题目描述
思路解析
一句话答案：LeetCode 347 前 K 个高频元素的经典解是哈希表数频次加大小为 k 的最小堆：把（频次，值）依次入堆，堆一超过 k 个就弹掉堆顶那个频次最低的，扫完堆里剩下的恰好是频次前 k 高的元素，时间 O(n log k)、空间 O(n+k)；追求线性时间可以换桶排序做到 O(n)。
这道题真正在问什么
给一个整数数组和数字 k，返回出现频率前 k 高的那些元素，顺序不限。它天然拆成两步：先数清每个数出现几次，再从这些频次里挑出最大的 k 个。第一步用哈希表数频次毫无悬念；这道题真正考的是第二步——「选前 k 大」怎么做得比全排序更聪明。
为什么不该把频次全排序
把所有（值，频次）按频次排序再取前 k 当然正确，但要 O(n log n)。浪费在哪？排序给出了全体元素的完整次序，而我们只关心「谁能进前 k」，前 k 之外的元素彼此谁大谁小根本无所谓。关键观察：只需要动态维护一个「目前最强的 k 个」的小圈子，新元素来了就和圈里最弱的比一比，更强就把最弱的踢出去。这个「随时找到圈内最弱者」的需求，正是堆的主场。
为什么用最小堆而不是最大堆
直觉常会反着走：求前 k 大不是该用最大堆吗？用最大堆得把全部元素建堆再连弹 k 次，堆的规模是 n。换成只装 k 个元素的最小堆，堆顶永远是圈子里频次最低的那个——恰好是随时要淘汰的对象：新元素入堆，一旦超过 k 个就弹掉堆顶，弱者出局、强者留下，堆始终只有 k 的规模。
两个容易翻车的点：一是堆的比较键必须是频次而不是数值本身，所以入堆的是（频次，值）这样的二元组；二是必须先用哈希表把频次统计完再入堆，直接把原数组元素怼进堆会把同一个值拆成多份，频次全错。
凭什么留在堆里的就是前 k 高
循环全程保持一个不变量：堆里装的始终是「到目前为止频次最高的至多 k 个元素」。每次被弹出的都是当前堆中频次最小的，它已经输给了堆里所有同伴；又因为频次在入堆之前就统计完毕、不会再变化，被淘汰者永远没有翻盘机会。所以全部元素处理完后，堆里剩下的 k 个就是全局频次前 k 高，正确性不依赖任何输入顺序。
复杂度多少，能做到 O(n) 吗
数组长度为 n 时，哈希表里的不同元素至多 n 个，每个各做一次入堆、至多一次弹出，每次 O(log k)，总时间 O(n log k)；空间 O(n+k)，哈希表存频次、堆只存 k 个。k 远小于 n 时比全排序省得多。
想彻底去掉 log 可以换桶排序：频次的取值范围只能是 1 到 n，开 n+1 个桶，把每个元素放进「下标等于它频次」的桶里，再从高频桶往低频桶倒着收集，凑满 k 个就停，整体 O(n)。面试先给堆解、再补一句桶排序的优化，是这道题的完整答案。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
为什么用「最小堆」而不是最大堆？因为我们要不停淘汰「频次最低」的，让频次最低的永远浮在堆顶，超员就弹它，省去对全部元素排序。
数频次。节点显示「值(×频次)」，堆按频次做最小堆——堆顶永远是当前频次最小的，超过 k 个就弹掉堆顶。
数频次。节点显示「值(×频次)」，堆按频次做最小堆——堆顶永远是当前频次最小的，超过 k 个就弹掉堆顶。
数频次。节点显示「值(×频次)」，堆按频次做最小堆——堆顶永远是当前频次最小的，超过 k 个就弹掉堆顶。
频次数完。节点显示「值(×频次)」，堆按频次做最小堆——堆顶永远是当前频次最小的，超过 k 个就弹掉堆顶。
准备进堆。节点显示「值(×频次)」，堆按频次做最小堆——堆顶永远是当前频次最小的，超过 k 个就弹掉堆顶。
入堆 1（×3）。节点显示「值(×频次)」，堆按频次做最小堆——堆顶永远是当前频次最小的，超过 k 个就弹掉堆顶。
1 入堆完成。节点显示「值(×频次)」，堆按频次做最小堆——堆顶永远是当前频次最小的，超过 k 个就弹掉堆顶。
入堆 2（×2）。节点显示「值(×频次)」，堆按频次做最小堆——堆顶永远是当前频次最小的，超过 k 个就弹掉堆顶。
比较 2(×2) 与父 1(×3)。节点显示「值(×频次)」，堆按频次做最小堆——堆顶永远是当前频次最小的，超过 k 个就弹掉堆顶。
上浮：2 换到上面。节点显示「值(×频次)」，堆按频次做最小堆——堆顶永远是当前频次最小的，超过 k 个就弹掉堆顶。
2 入堆完成。节点显示「值(×频次)」，堆按频次做最小堆——堆顶永远是当前频次最小的，超过 k 个就弹掉堆顶。
入堆 3（×1）。节点显示「值(×频次)」，堆按频次做最小堆——堆顶永远是当前频次最小的，超过 k 个就弹掉堆顶。
比较 3(×1) 与父 2(×2)。节点显示「值(×频次)」，堆按频次做最小堆——堆顶永远是当前频次最小的，超过 k 个就弹掉堆顶。
上浮：3 换到上面。节点显示「值(×频次)」，堆按频次做最小堆——堆顶永远是当前频次最小的，超过 k 个就弹掉堆顶。
3 入堆完成。节点显示「值(×频次)」，堆按频次做最小堆——堆顶永远是当前频次最小的，超过 k 个就弹掉堆顶。
弹出堆顶 3（×1）。节点显示「值(×频次)」，堆按频次做最小堆——堆顶永远是当前频次最小的，超过 k 个就弹掉堆顶。
末尾 2 补到堆顶。节点显示「值(×频次)」，堆按频次做最小堆——堆顶永远是当前频次最小的，超过 k 个就弹掉堆顶。
堆已恢复最小堆。节点显示「值(×频次)」，堆按频次做最小堆——堆顶永远是当前频次最小的，超过 k 个就弹掉堆顶。
淘汰 3（×1），堆恢复大小 2。节点显示「值(×频次)」，堆按频次做最小堆——堆顶永远是当前频次最小的，超过 k 个就弹掉堆顶。
堆里最终留下 1(×3) 和 2(×2)（绿色）= 前 2 个高频元素。3(×1) 因频次最低被弹出。按频次排好 = 答案 [1, 2]。
边界都不破坏「最小堆筛 k 个」的主逻辑。
两个高频追问：桶排序 O(n) 优化、流式场景的近似 Top-K。
参考代码
import heapqfrom collections import Counterdef topKFrequent(nums, k): cnt = Counter(nums) # 1) 数频次 heap = [] # 最小堆：(频次, 值) for val, fr in cnt.items(): heapq.heappush(heap, (fr, val)) if len(heap) > k: # 超员 heapq.heappop(heap) # 弹掉频次最小的 return [val for fr, val in heap]复杂度
- 时间：O(n log k)，n 个不同元素各做一次 O(log k) 的堆操作
- 空间：O(n + k)，哈希表 O(n) 存频次，堆 O(k)
易错点
面试追问把动画讲成自己的话
追问能不能做到 O(n)？
追问如果数据是流式、不能一次性数完频次怎么办？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
字符串的编码与解码
LeetCode 271 · 中等 · 沿着 数组 & 哈希 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题