给定一个整数数组 nums 和一个整数 k，请返回其中出现频率前 k 高的元素，要求时间复杂度优于 O(n log n)。
示例：[1,1,1,2,2,3], k=2 → [1,2]。
腾讯变体原题："设计一个算法来统计海量数据中出现次数最多的前 K 个元素。"
上一篇
LC 215 讲了 TopK 在
值轴上的选择（快速选择）。这一篇换一根轴：键从"值"换成"
频率" —— 就是这一换，出现了快速选择没有的结构性免费。
一、题目与语义
1.1 门槛：优于 O(n log n)
先哈希计数一遍（O(n)），数出每个值出现的频率。这一步没有任何技巧。剩下的问题是：
按频率挑出前 k 个值 —— 又是一个 TopK。
如果这时对
(值, 频率) 对按频率排个序，O(n log n)，题目就卡在这：
必须优于 O(n log n)。所以候选只剩两条路：
- 小根堆：O(n log k) —— k 小时够快；
- 桶排序：O(n) —— 这题真正的正解，也是本文的主角。
1.2 语义：返回的是 k 个不同的值
和 LC 215 的"重复各占位置"正好相反：
347 返回的是 k 个不同的元素，每个值只出现一次。两题题面像，语义却镜像 —— 做的时候别串。
（LC 215 里官方例 2 专门钉死了"第 k 大是位置不是不同值"；347 这里反过来，返回的是 distinct 值集合。）
题目保证答案唯一，所以不会出现"频率并列卡在边界上"的歧义。
二、桶排序：频率是天然的桶下标
2.1 核心观察
计数完成之后，一个值的出现频率
最少是 1、最多是 n（全体都是它）—— 也就是说：
频率天然落在 [1, n] 这个小整数区间里。
要排序的键恰好是一个范围已知的小整数 —— 这正是
计数排序的前提。于是"按频率排序"免费：建
n+1 个桶，
频率是多少就丢进下标多少的桶，一次比较都不用做。收集时从桶
n 往桶
1 扫，收满 k 个停。
对比一下：堆每插一个元素要 O(log k)，桶入桶是实打实的 O(1)。
当你发现要排序的键恰好是一个很小的整数范围，排序就可以免费 —— 这个思想和计数排序同源。
2.2 逐帧推演
官方例：
[1,1,1,2,2,3]，
k = 2。
13 帧（与状态机
bucketTopKSteps.js 逐行核对过）：
看第 7-9 帧：
那三个空桶不是浪费 —— 它们是"从高频往低频扫"这个动作的字面展示。频率 6、5、4 都没有对应的值，说明这个数组里没有元素出现那么多次；收集指针扫过它们，正说明桶下标和频率一一对应、不重不漏。
from collections import Counter
def topKFrequent(nums, k):
freq = Counter(nums)
buckets = [[] for _ in range(len(nums) + 1)]
for v, f in freq.items():
buckets[f].append(v) # 频率即下标，O(1) 入桶
ans = []
for f in range(len(nums), 0, -1):
for v in buckets[f]:
ans.append(v)
if len(ans) == k:
return ans
return ans
三步全是 O(n)，
总计 O(n) —— 比题目划的红线还低一档。代价是 O(n) 的桶空间，以及一个小前提：
频率是整数、且范围已知（这题天然满足）。
三、堆版：O(n log k) 的通用路
如果键的值域没有这种保证（比如按"距离"挑前 k 个），桶就没了，堆是通用解：
import heapq
def topKFrequent(nums, k):
freq = {}
for x in nums:
freq[x] = freq.get(x, 0) + 1
heap = []
for v, f in freq.items():
heapq.heappush(heap, (f, v)) # 按频率比的小根堆
if len(heap) > k:
heapq.heappop(heap)
return [v for f, v in heap]
对
(频率, 值) 对维护容量 k 的小根堆：堆顶是"当前 k 个候选里频率最小的"，新元素想进前 k 先打赢门槛 —— 和 LC 215 的堆是同一个思想，只是比较器从值换成了频率。
两条路的对照
桶排序赢在渐近和常数，堆赢在通用和内存 —— k 远小于 distinct 数且键没有范围保证时，堆是唯一选择。
四、复杂度对照
注意桶排序的 O(n) 有三部分：计数 O(n)、入桶 O(distinct)、收集最多扫 n+1 个桶 —— 全是线性，合计 O(n)。它比堆省掉的那个 log k，正是"键的值域当下标"换来的。
五、腾讯变体：海量数据的前 K 个高频元素
"设计一个算法来统计海量数据中出现次数最多的前 K 个元素。"
和上一篇的"10 亿个数找前 100 大"相比，这题多了一层麻烦：
去重后的元素表本身可能就装不进内存。10 亿条日志里的不同 URL 可能上亿个，平均 50 字节就是好几 GB —— 连哈希计数表都建不起来。
标准做法是
哈希分桶 + 局部 TopK + 归并：
- 分：对每个元素算
hash(x) % 1000，写入 1000 个小文件。同一元素必然落进同一文件 —— 这是分治正确性的根据：任何元素的完整计数都在一个文件里，不会被打散；
- 治：每个小文件平均只有 100 万条，单独建哈希计数 + 小根堆（或桶排序），各取自己的前 100；
- 合：1000 个局部 Top100 归并成全局 Top100 —— 10 万条，随便放。
单机多进程就能做，天然可扩到多机 —— 每台机器负责一批桶。这个套路是
外部排序的分治框架，只不过把"排序"换成了"TopK"。
对照上一篇：
10 亿个数找前 100 大连分桶都不用 —— 数字本身可比较、单遍扫描 + 容量 100 的小根堆就够，因为"候选"只有 100 个；而这题多出的那层"去重表装不下"，才逼出了分桶。
海量题目的分水岭永远是：单机内存里必须装下什么？ 装得下 k 个候选 → 堆；连 distinct 集合都装不下 → 分桶分治。
六、Java 版
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int x : nums) freq.merge(x, 1, Integer::sum);
List<List<Integer>> buckets = new ArrayList<>();
for (int i = 0; i <= nums.length; i++) buckets.add(new ArrayList<>());
for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
buckets.get(e.getValue()).add(e.getKey()); // 频率即下标
}
int[] ans = new int[k];
int idx = 0;
for (int f = nums.length; f >= 1 && idx < k; f--) {
for (int v : buckets.get(f)) {
ans[idx++] = v;
if (idx == k) break;
}
}
return ans;
}
}
堆版（
PriorityQueue 默认小根堆，比较器按频率）：
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[1] - b[1]);
for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
heap.offer(new int[]{e.getKey(), e.getValue()});
if (heap.size() > k) heap.poll();
}
七、边界情况与常见坑
坑一：给桶排序忘了"频率并列"。 同一频率的多个值在同一个桶里，收集顺序由入桶顺序决定。本题保证答案唯一，所以不会踩；但如果面试变体允许并列（比如 LC 692 要求并列按字典序），桶内还要再排一次。
坑二：堆版比较器写反。 要的是"频率最小的在堆顶"，比较器是
a[1] - b[1] 升序；写成降序就变成大根堆，弹掉的恰恰是频率最高的。
坑三：桶数组大小。 频率上限是
n 不是
max(freq) —— 建
n+1 个桶（下标 0 到 n）。下标 0 永远空（频率至少 1），多建一格没坏处，少建一格越界。
坑四：题目红线是"优于 O(n log n)"。 计数后直接对 distinct 列表排序（O(m log m)，m ≤ n）最坏仍是 O(n log n)，卡线不过 —— 这正是题目逼你写堆或桶的原因。
八、变体
一图流的选择：
键是小整数范围 → 桶排序 O(n)；键任意 + 只要前 k → 小根堆；静态全量 + 键任意 → 快速选择。
九、面试怎么答
- 先说框架：哈希计数 O(n)，然后按频率挑前 k —— 点破这就是 TopK；
- 给正解：桶排序 O(n)，讲清"频率天然在 [1, n]"这个结构性前提；
- 备选：堆 O(n log k)，讲清它不依赖键的值域、流式友好；
- 被追问海量数据：哈希分桶（同元素必落同桶）→ 局部 TopK → 归并；点出与"10 亿找前 100 大"的分水岭是去重表是否装得下内存；
- 自测：
topKFrequent([1,1,1,2,2,3], 2) == [1,2]；
- 一句话总结：要排序的键恰好是小整数范围时，排序免费 —— 频率天然在 [1, n]，桶下标就是它的排名。
系列上一篇：【LC 215】数组中的第 K 个最大元素。本文动画 13 帧，与状态机单测（19 例，与计数排序/小根堆两个独立参考解三向交叉验证）逐行核对过。