347. Top K Frequent Elements

/**
 * 找出数组中出现频率前 k 高的元素
 * @param {number[]} nums - 输入的整数数组
 * @param {number} k - 需要返回的高频元素个数
 * @returns {number[]} - 包含出现频率前 k 高的元素的数组
 */
var topKFrequent = function (nums, k) {
  // 第一步：统计数组中每个元素的出现次数
  // 创建一个 Map 结构，key 为数组元素，value 为该元素出现的次数
  const cnt = new Map()
  // 遍历输入数组，逐个统计元素出现次数
  for (const x of nums) {
    // 如果元素已存在，获取其当前计数；否则默认计数为 0
    // 然后将计数加 1，并更新到 Map 中
    cnt.set(x, (cnt.get(x) ?? 0) + 1)
  }
  // 获取所有元素的最高出现次数（用于确定桶的最大容量）
  const maxCnt = Math.max(...cnt.values())

  // 第二步：使用桶排序的思想，按出现次数分组元素
  // 创建一个数组作为桶，数组长度为 maxCnt + 1（索引从 0 到 maxCnt）
  // 每个桶的初始值都是一个空数组，用于存放对应出现次数的元素
  const buckets = Array.from({ length: maxCnt + 1 }, () => [])
  // 遍历统计好的元素-次数键值对
  for (const [x, c] of cnt.entries()) {
    // 将元素 x 放入对应出现次数 c 的桶中
    buckets[c].push(x)
  }

  // 第三步：从高频到低频遍历桶，收集前 k 个高频元素
  // 初始化结果数组
  const ans = []
  // 从最高出现次数的桶开始倒序遍历
  // 循环终止条件：遍历完所有桶 或 结果数组已收集到 k 个元素
  for (let i = maxCnt; i >= 0 && ans.length < k; i--) {
    // 将当前桶中的所有元素扩展到结果数组中
    // （题目保证答案唯一，因此不会出现需要截断的情况）
    ans.push(...buckets[i])
  }
  // 返回最终收集到的前 k 个高频元素
  return ans
}

const buckets = Array.from({ length: maxCnt + 1 }, () => []);：这行代码的核心目的是：创建一个长度为 maxCnt + 1 的数组（我们称之为「桶数组」），并且数组中的每一个位置都预先初始化一个空数组。

Array(maxCnt + 1).fill([]) 和 Array.from({ length: maxCnt + 1 }, () => []) 是否等价，这是一个非常关键的细节问题，两者表面看起来效果相似，但实际行为完全不同，核心区别在于「是否创建独立的数组」。

两者不一样，Array.fill([]) 会导致所有位置共享同一个空数组，而 Array.from() 会为每个位置创建独立的空数组

fill() 方法的特性是：将传入的参数作为「同一个值」填充到数组的所有位置。这里传入的 [] 是一个数组对象（引用类型），因此数组的每一个位置都会指向同一个内存地址的空数组。

方法：哈希表 + 小顶堆（优先队列，最优解之一）

核心思路

这是面试中更常考察的「最优解」，兼顾时间和空间效率：

先用哈希表统计每个元素的出现频率；
维护一个大小为 k 的小顶堆（堆顶是堆中频率最小的元素）；
遍历哈希表的元素：
- 若堆的大小 < k：直接入堆；
- 若堆的大小 = k：比较当前元素频率与堆顶频率，若当前频率更大，则弹出堆顶，将当前元素入堆；
最终堆中的 k 个元素就是频率前 k 高的元素。