leetcode-347 前 K 个高频元素

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function (nums, k) {
  const map = new Map();
  for (const num of nums) {
    const count = map.get(num) || 0;
    map.set(num, count + 1);
  }
  const arr = Array.from(map.entries());
  arr.sort((a, b) => {
    const [, aVal] = a;
    const [, bVal] = b;
    return bVal - aVal;
  });
  return arr.slice(0, k).map((o) => o[0]);
};
// console.log(topKFrequent([1, 1, 1, 2, 2, 3], 2));

/**
 * @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 heap = [];
  for (const [num, freq] of map.entries()) {
    if (heap.length < k) {
      heap.push([num, freq]);
      // 按频率升序
      heap.sort((a, b) => a[1] - b[1]);
    } else if (freq > heap[0][1]) {
      heap[0] = [num, freq];
      heap.sort((a, b) => a[1] - b[1]);
    }
  }
  return heap.map((pair) => pair[0]);
};
// console.log(topKFrequent([1, 1, 1, 2, 2, 3], 2));