前K个高频元素

/*
 * 题目：前K个高频元素
 * 要求：输入整数数组 nums 和整数 k，返回出现频率最高的 k 个不同元素；结果按频率降序，频率相同时按数值升序。k 范围为 0 到不同元素个数，k=0 返回 []。
 * 示例：输入 nums=[1,1,1,2,2,3]、k=2，返回 [1,2]；[4,4,3,3]、k=2 返回 [3,4]。
 */
function topKFrequent(nums, k) {}
console.log(topKFrequent([1, 1, 1, 2, 2, 3], 2)); // 预期：[1, 2]
console.log(topKFrequent([4, 4, 3, 3, 2], 2)); // 预期：[3, 4]
console.log(topKFrequent([], 0)); // 预期：[]
console.log(topKFrequent([5, 5, 6], 0)); // 预期：[]

function topKFrequent(nums, k) {
  const counts = new Map();
  for (const value of nums) counts.set(value, (counts.get(value) || 0) + 1);
  if (!Number.isInteger(k) || k < 0 || k > counts.size)
    throw new RangeError("invalid k");
  const heap = [];
  const worse = (a, b) =>
    a.count !== b.count ? a.count < b.count : a.value > b.value;
  const swap = (a, b) => {
    [heap[a], heap[b]] = [heap[b], heap[a]];
  };
  function up(i) {
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (!worse(heap[i], heap[p])) break;
      swap(i, p);
      i = p;
    }
  }
  function down(i) {
    while (true) {
      let best = i;
      const l = i * 2 + 1;
      const r = l + 1;
      if (l < heap.length && worse(heap[l], heap[best])) best = l;
      if (r < heap.length && worse(heap[r], heap[best])) best = r;
      if (best === i) return;
      swap(i, best);
      i = best;
    }
  }
  for (const [value, count] of counts) {
    heap.push({ value, count });
    up(heap.length - 1);
    if (heap.length > k) {
      swap(0, heap.length - 1);
      heap.pop();
      down(0);
    }
  }
  return heap
    .sort((a, b) => b.count - a.count || a.value - b.value)
    .map((item) => item.value);
}

// 三组以上可直接运行的验证。
console.log(topKFrequent([1, 1, 1, 2, 2, 3], 2)); // 预期：[1, 2]
console.log(topKFrequent([4, 4, 3, 3, 2], 2)); // 预期：[3, 4]
console.log(topKFrequent([], 0)); // 预期：[]
console.log(topKFrequent([5, 5, 6], 0)); // 预期：[]