题目

给你一个整数数组 nums 和一个整数 k，请你返回其中出现频率前 k 高的元素。你可以按任意顺序返回答案。

示例：

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

解释：

• 1 出现了 3 次
• 2 出现了 2 次
• 3 出现了 1 次

频率最高的两个元素是 1 和 2。

约束：

• 1 <= nums.length <= 10^5
• k 的取值范围是 [1, 数组中不同元素的个数]
• 题目保证答案唯一

思路

这题可以拆成两步：

1. 统计每个元素出现的频率。
2. 按频率从高到低，取出前 k 个元素。

统计频率用哈希表，时间复杂度是 O(n)。

难点在第二步。常见做法是排序或使用堆：

• 排序：把元素按频率排序，时间复杂度 O(n log n)。
• 最小堆：维护大小为 k 的堆，时间复杂度 O(n log k)。

这题还可以做到 O(n)，因为频率有一个天然的上界：一个元素最多出现 nums.length 次。

于是可以创建一个桶数组：

buckets[count] = 所有出现 count 次的元素

桶的下标就是频率，不需要比较大小。统计完成后，从最大的下标开始往前遍历，依次取出元素，直到收集到 k 个。

代码

function topKFrequent(nums, k) {
  const freq = new Map();

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

  const buckets = Array.from({ length: nums.length + 1 }, () => []);

  for (const [num, count] of freq) {
    buckets[count].push(num);
  }

  const result = [];

  for (let count = nums.length; count > 0 && result.length < k; count--) {
    for (const num of buckets[count]) {
      result.push(num);
      if (result.length === k) {
        return result;
      }
    }
  }

  return result;
}

调用示例：

console.log(topKFrequent([1, 1, 1, 2, 2, 3], 2));
// [1, 2]

执行过程

以 nums = [1,1,1,2,2,3]，k = 2 为例。

第一步，统计频率：

1 -> 3
2 -> 2
3 -> 1

第二步，把元素放进对应频率的桶：

buckets[3] = [1]
buckets[2] = [2]
buckets[1] = [3]

第三步，从高频往低频遍历：

count = 3，取出 1
count = 2，取出 2

已经收集到 2 个元素，返回 [1, 2]。

复杂度

时间复杂度：O(n)

• 遍历数组统计频率：O(n)
• 遍历哈希表放入桶：O(n)
• 从高频到低频遍历桶：最多 O(n)

空间复杂度：O(n)

• 哈希表最多存 n 个不同元素
• 桶数组长度为 n + 1
• 结果数组最多存 k 个元素

桶和堆的区别

这里的桶不是堆。

桶是一个数组，下标表示频率，buckets[count] 存放所有出现 count 次的元素。它利用频率范围固定在 1..n，直接按下标定位。

堆通常指优先队列，用完全二叉树维护最值，适合动态维护前 k 个元素。用最小堆解这道题的时间复杂度是 O(n log k)。

两者都能解决 Top K 问题，但桶排序在这个场景下少了对频率的比较和调整，因此可以做到 O(n)。

最后

这道题的核心不是排序，而是利用频率的取值范围做计数。

记住三个步骤：

1. 用 Map 统计频率。
2. 用频率作为下标，把元素放进桶里。
3. 从高频桶往低频桶取，凑够 k 个就返回。

当题目中的值域或频率范围有限时，桶排序往往能把 O(n log n) 降到 O(n)。