题目描述
给数组 nums 和整数 k，返回出现频率最高的 k 个元素。
nums = [1, 1, 1, 2, 2, 3]
k = 2
输出 = [1, 2]
思路解析
统计完次数再全排序能做，可我们只要前 k 个，把所有元素排得明明白白太浪费。
先用哈希表数出每个数的次数，再开一排桶，把元素丢进「次数对应的桶」。次数最多就 n，所以桶的数量有限。
从下标最大（次数最高）的桶开始往回扫，依次把里面的元素收走，收满 k 个就停。
第一步：数次数：先扫一遍数组，用哈希表记下每个数出现几次（这一步是后面装桶的原料）。
第二步：按次数装桶：数完了：1 进「3 次」桶、2 进「2 次」桶、3 进「1 次」桶。注意桶是按次数分的，次数再大也超不过 n 个。
第三步：从高频桶往回取：从最高频的桶开始取：「3 次」桶里是 1，收走，已经有 1 个。
再取「2 次」桶：再取「2 次」桶里的 2，已经够 k=2 个了，停。答案 [1, 2]，根本没碰到「1 次」桶。
Top K 高频的通杀思路：先哈希计数，再拿「次数」当桶下标。次数范围有限，桶排序就能避开整体排序。
参考代码（Python）
Python
1def topKFrequent(nums, k):
2 from collections import Counter
3 cnt = Counter(nums) # 数次数
4 buckets = [[] for _ in range(len(nums) + 1)]
5 for x, c in cnt.items():
6 buckets[c].append(x) # 按次数装桶
7 res = []
8 for c in range(len(buckets) - 1, 0, -1): # 从高频往回扫
9 for x in buckets[c]:
10 res.append(x)
11 if len(res) == k: return res复杂度分析
- 时间复杂度：O(n) —— 计数 + 装桶 + 扫桶
- 空间复杂度：O(n) —— 哈希表 + 桶
套路模板
工程里常用堆解法：维护大小为 k 的小顶堆，频率比堆顶大就替换，O(n log k)。nlargest 一行就是这个意思。
Python
1import heapq
2from collections import Counter
3cnt = Counter(nums)
4# 维护一个大小为 k 的小顶堆，堆顶是 k 个里最小频率
5return heapq.nlargest(k, cnt.keys(), key=cnt.get)易错点
- ❌ 桶数组开 len(nums) 大 → ✅ 开 len(nums) + 1（出现次数最多可达 n，要能放下下标 n，所以长度是 n+1）
- ❌ 从下标 0 的桶开始扫 → ✅ 从最大下标往 1 倒扫（要的是「高频」，必须从次数大的桶开始取）
- ❌ 用堆时建大小为 n 的堆 → ✅ 只维护大小为 k 的小顶堆（堆里只留 k 个才是 O(n log k)，留 n 个就退化成排序了）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。