手写算法：前 K 个高频元素

347. 前 K 个高频元素

哈希表 + 数组排序

function topKFrequent(nums, k) {
  let map = new Map();
  let list = [];

  for (let i = 0; i < nums.length; i++) {
    const item = nums[i];
    map.set(item, (map.get(item) || 0) + 1);
  }

  for (let [key, value] of map.entries()) {
    list.push([key, value]);
  }

  // 降序排列，频率高的才会出现在前面
  list.sort((a, b) => b[1] - a[1]);
  return list.slice(0, k).map(([value]) => value);
}

最小堆

没学会，抄的答案

最小堆，顾名思义堆顶最小。

1. 建立一个最小堆

2. 插入堆的元素，此时小于 k，可直接插入；若等于 k，则需要将堆顶与插入进来的值进行比较，若堆顶大于当前的值，则舍弃。反之，则弹出堆顶，将当前值插入堆中。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
  const map = new Map();

  for (const num of nums) {
    map.set(num, (map.get(num) || 0) + 1);
  }

  // 创建小顶堆
  const priorityQueue = new PriorityQueue((a, b) => a[1] - b[1]);

  // entry 是一个长度为2的数组，0位置存储key，1位置存储value
  for (const entry of map.entries()) {
    priorityQueue.push(entry);
    if (priorityQueue.size() > k) {
      priorityQueue.pop();
    }
  }

  let ret = [];

  for (let i = priorityQueue.size() - 1; i >= 0; i--) {
    ret[i] = priorityQueue.pop()[0];
  }

  return ret;
};

function PriorityQueue(compareFn) {
  this.compareFn = compareFn;
  this.queue = [];
}

// 添加
PriorityQueue.prototype.push = function(item) {
  this.queue.push(item);
  let index = this.queue.length - 1;
  let parent = Math.floor((index - 1) / 2);
  // 上浮
  while (parent >= 0 && this.compare(parent, index) > 0) {
    // 交换
    [this.queue[index], this.queue[parent]] = [this.queue[parent], this.queue[index]];
    index = parent;
    parent = Math.floor((index - 1) / 2);
  }
};

// 获取堆顶元素并移除
PriorityQueue.prototype.pop = function() {
  const ret = this.queue[0];

  // 把最后一个节点移到堆顶
  this.queue[0] = this.queue.pop();

  let index = 0;
  // 左子节点下标，left + 1 就是右子节点下标
  let left = 1;
  let selectedChild = this.compare(left, left + 1) > 0 ? left + 1 : left;

  // 下沉
  while (selectedChild !== undefined && this.compare(index, selectedChild) > 0) {
    // 交换
    [this.queue[index], this.queue[selectedChild]] = [this.queue[selectedChild], this.queue[index]];
    index = selectedChild;
    left = 2 * index + 1;
    selectedChild = this.compare(left, left + 1) > 0 ? left + 1 : left;
  }

  return ret;
};

PriorityQueue.prototype.size = function() {
  return this.queue.length;
};

// 使用传入的 compareFn 比较两个位置的元素
PriorityQueue.prototype.compare = function(index1, index2) {
  if (this.queue[index1] === undefined) {
    return 1;
  }
  if (this.queue[index2] === undefined) {
    return -1;
  }

  return this.compareFn(this.queue[index1], this.queue[index2]);
};

手写题：实现断点续传

请使用 vue 或者 react 实现断点续传

React + Node 实现大文件分片上传、断点续传、秒传思路