题目描述
给数组 nums 和整数 k，返回出现频率最高的 k 个元素。
思路解析
最直接的想法：用哈希表数出每个数的次数，再把所有数按次数从大到小排序，取前 k 个。能对，但我们只要前 k 个，却把每个数都排得明明白白，多花了 log n 的排序，浪费。
转折：一个数最多出现 n 次，所以「次数」的取值只有 0~n 这有限几种。开一排桶，桶下标 = 出现次数，把每个数丢进「它次数对应的桶」。再从下标最大(次数最高)的桶往回扫，凑够 k 个就停——这样避开了对全部元素的整体排序，整体只 O(n)。
数次数 · 看第 1 个 1：第一步先扫一遍数组数次数。看到第一个 1，哈希表里 cnt[1] 记为 1。
数次数 · 第 2、3 个 1：又遇到两个 1，cnt[1] 累加到 3。计数就是「见一个加一个」，哈希表查改都是 O(1)。
数次数 · 看 2：遇到第一个 2，cnt 里新增 cnt[2]=1。
数次数 · 第 2 个 2：又一个 2，cnt[2] 累加到 2。
数次数 · 看 3 · 计数完成：最后一个 3，cnt[3]=1。数组扫完，得到每个数的次数：1→3、2→2、3→1。这就是装桶的原料。
装桶 · 桶下标 = 出现次数：第二步装桶：遍历 cnt，把每个数丢进「它次数对应的桶」。1 进「次数 3」桶、2 进「次数 2」桶、3 进「次数 1」桶。注意桶是按次数分的，次数再大也超不过 n，所以桶的数量有限——这正是能用桶排序的根。
取 Top K · 先扫「次数 3」桶：第三步从下标最大(次数最高)的桶往回扫。先看「次数 3」桶，里面是 1，收走，res=[1]，已有 1 个，还差 1 个凑够 k=2。
取 Top K · 再扫「次数 2」桶 · 凑够：往回到「次数 2」桶，取出 2，res=[1,2]，凑够 k=2 个，立刻停。「次数 1」桶根本没碰——这就是比整体排序省的地方：低频的数压根不用管。答案 [1, 2]。
Top K 高频的通杀思路：先哈希计数，再拿「次数」当桶下标。只要某个量(次数、分数、年龄)取值范围有限，桶排序就能避开 O(n log n) 的整体排序。
参考代码（Python）
1def topKFrequent(nums, k):
2 from collections import Counter
3 cnt = Counter(nums) # 数次数: 1→3, 2→2, 3→1
4 buckets = [[] for _ in range(len(nums) + 1)] # 桶下标 0~n
5 for x, c in cnt.items():
6 buckets[c].append(x) # 按次数 c 装桶
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 # 凑够 k 个就停复杂度分析
- 时间复杂度：O(n) —— 计数 O(n) + 装桶 O(不同元素数) + 倒扫桶 O(n)，都是线性，没有 log n 的排序
- 空间复杂度：O(n) —— 哈希表存至多 n 个不同的数 + 长为 n+1 的桶数组
套路模板
工程里常用堆解法：维护大小为 k 的小顶堆，频率比堆顶大就替换，堆里始终只留 k 个，O(n log k)。一行 nlargest 就是这个意思，省内存且不依赖「次数有界」。
1import heapq
2from collections import Counter
3cnt = Counter(nums)
4# 维护一个大小为 k 的小顶堆，堆顶永远是当前 k 个里频率最小的
5return heapq.nlargest(k, cnt.keys(), key=cnt.get) # O(n log k)易错点
- 错误写法：直接对所有数按频率 sorted 再切前 k → 正确写法：用桶(次数当下标)或大小为 k 的小顶堆（只要前 k 个却把全部 n 个排了序，白搭 O(n log n)；桶排序 O(n)、堆 O(n log k) 都更省）
- 错误写法：桶数组开 len(nums) 这么长 → 正确写法：开 len(nums) + 1，因为次数最大可达 n（一个数最多出现 n 次，要能放下下标 n，桶长必须是 n+1，否则 buckets[n] 越界）
- 错误写法：从下标 0 的桶开始顺着扫 → 正确写法：从最大下标往 1 倒着扫（要的是「高频」，必须先取次数大的桶；顺扫会先拿到低频元素，答案全错）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。