前K个高频元素：堆、快速选择、桶排序三种解法全解析

LeetCode Hot 100 里的第 347 题“前K个高频元素”，是我跟人聊算法时最常推荐拿来当“堆专题入门第一题”的一道题。题目描述很简短，给你一个整数数组和一个 k，让你返回数组里出现频率前 k 高的元素，顺序不限。但就是这么一道看似“人畜无害”的题，实际上把哈希表统计、堆、快速选择、桶排序这四类高频考点全串起来了，在 Hot 100 里属于少有的“一题多吃”型题目。

我自己刷这道题前前后后换过三种写法，每次重刷都有新收获。如果你是刚开始刷 LeetCode 的同学，用它来练“Top K 问题”的通用思路，再合适不过；如果你已经刷过一遍，手里的解法可能只有堆，那我强烈建议你把快速选择和桶排序也写一遍，这对理解“面试中如何给优化方向”特别有帮助。这篇文章我就把三种主流解法的思路、代码、复杂度、选型逻辑，以及我实际踩过的坑全部拆开讲清楚。

1. 题目拆解与核心思路分析

1.1 先别急着写代码，把题目翻译成人话

原题输入是nums = [1,1,1,2,2,3]，k = 2，输出应该是[1, 2]。理由很简单：1 出现 3 次，2 出现 2 次，3 出现 1 次，取前两名的元素就是 1 和 2。

很多新手一上来就想到“那我先数每个数字出现多少次，然后排序取前 k 个不就行了”。思路没错，但问题在于，这道题考的不是“能不能做出来”，而是“你能不能把时间复杂度从 O(n log n) 压下来”。题目里数组长度 n 可以达到 10 的 5 次方甚至更大，面试官一定会追问一句：“如果 n 特别大，k 特别小，你怎么优化？”

所以第一步，我们得把问题拆成两个独立阶段：

• 阶段一：统计频次。这一步几乎没得选，就是哈希表。遍历一次数组，用字典记录每个元素出现的次数，时间复杂度 O(n)，空间复杂度 O(n)。
• 阶段二：从字典的 n 个键值对里，选出频次最高的 k 个。这个“选 Top K”才是本题真正的考核点。

想明白这两段式结构，你就会意识到：如果你在阶段二直接对全部键值对排序，那就是暴力的 O(n log n)，属于“能做但不够优”；如果你能利用“只关心前 k 个”这个信息，就可以把复杂度降下来。

1.2 为什么这道题适合反复刷

我第一次刷这道题的时候，只觉得“用堆好像挺巧妙”，但没有深入去想为什么堆是对的。后来二刷、三刷，才慢慢想明白：凡是“求最大/最小前 k 个”的问题，基本都能套同一个模板——用小顶堆维护“当前最小的那个候选”，让堆的大小始终保持 k。这个模板不止能解这道题，还能解“前 K 个最小数”“合并 K 个有序链表”“滑动窗口最大值（配合堆变体）”等一片题目。

另外这题还有一层价值：它让你理解了“频率”这种数据的特殊结构。频率值有一个天然范围，最小是 1，最大不超过数组长度。正是因为频次范围是有限的，桶排序那种“用频率做下标”的奇技淫巧才有落户的空间。如果你只见过堆写法，等面试官问“还有没有 O(n) 的做法”时，你会有点懵。

1.3 题目边界条件先看清

在做任何方案之前，有几个边界条件一定要确认：k 是否可能等于 0？题目保证 k 合法，一般 1 <= k <= 数组中不同元素的个数，但实际写代码时最好防御性处理。数组为空时直接返回空列表即可。另外题目说“可以按任意顺序返回答案”，这意味着你不需要在结果上做任何排序，只要能保证取出来的元素集合正确就行，这给快速选择和桶排序留下了很大的实现空间。

2. 方案一：小顶堆维护前 K（面试首选）

2.1 为什么是“小顶堆”，而不是“大顶堆”

这是很多初学者最容易卡住的地方。直觉上，要求“频率最高的前 k 个”，那不是应该用大顶堆吗？堆顶最大，一个个取不就行了？

但你要意识到：如果维护一个大顶堆，堆顶是当前频率最大的元素，那当你遍历新的元素时，你很难判断“新元素”和“堆里某个较弱的元素”之间该淘汰谁。你只能把所有元素都丢进大顶堆，最后再弹 k 次，这样时间是 O(n log n)。

反过来，小顶堆的思路是：我只要保证堆里存的是“到目前为止所见元素里频率最高的 k 个”，并且堆顶是这 k 个里最小的那个。来了一个新元素，如果它的频次比堆顶还大，说明它能挤进前 k，那就先把最弱的堆顶淘汰掉，再把它加进来。整个过程堆的大小一直保持在 k，插入和删除的复杂度都是 O(log k)。遍历 n 个键值对，就是 O(n log k)。

所以结论很清晰：不是用大顶堆去“取最大”，而是用小顶堆去“淘汰最小”。这个思维反差是解开 Top K 问题的一把钥匙。

2.2 完整实现与代码细节

from collections import Counter import heapq def top_k_frequent(nums, k): # 1. 统计频次 freq_map = Counter(nums) # 2. 用大小为 k 的小顶堆筛选 heap = [] for num, freq in freq_map.items(): heapq.heappush(heap, (freq, num)) if len(heap) > k: heapq.heappop(heap) # 3. 堆里剩下的就是频次前 k 的元素 return [num for _, num in heap]

这里有一个容易被忽略的细节：把(freq, num)作为整体放进堆。Python 的heapq在比较元组时会先比较第一个元素，也就是 freq；如果两个元组的 freq 相等，就会接着比较 num。这在频率相同的情况下，可能导致堆保留谁、淘汰谁发生微妙的差异，但因为题目只要求元素集合正确，同频元素谁在前、谁在后无所谓，所以这个实现是安全的。

还有一个小技巧：Python 里Counter帮你省掉了手动写字典遍历的代码，但你面试时，最好还是能把“手动统计频次”这个版本也说出来：

freq_map = {} for num in nums: freq_map[num] = freq_map.get(num, 0) + 1

因为有些面试官会追问Counter的实现，你懂底层会更占优势。

2.3 复杂度到底怎么算，怎么跟面试官讲

时间复杂度分两块：统计频次是 O(n)，堆操作是 O(n’ log k)，其中 n’ 是数组中不同元素的个数，n’ <= n。所以整体记为 O(n log k)。空间复杂度方面，哈希表需要 O(n’，实际为 O(n)）的空间，堆需要 O(k)，所以整体空间复杂度是 O(n)。

跟面试官讲的时候，我一般会补一句：“当 k 远小于 n 时，这个方案比直接排序好很多；当 k 接近 n 时，两者差别不大，但堆方案仍然能保证不会做多余的排序。”这句话能让对方觉得你不是在背代码，而是真的考虑过复杂度边界。

2.4 堆方案的实操心得

这里分享几个我踩过的坑：

第一，有人会把heapq.nsmallest(k, freq_map.keys(), key=lambda x: freq_map[x])当作一行流写法。这个写法虽然正确，看起来也优雅，但实际上它内部也是用堆实现的。我建议你在面试初期不要直接用，因为一旦面试官让你解释底层，你没准会卡壳。先手写 push/pop 逻辑，后面展示优化时可提一句“标准库里还有更简洁的 nsmallest”。

第二，堆元素写成(num, freq)和(freq, num)是有区别的。如果你写成(num, freq)，堆排序依据的是数字大小而不是频率，结果根本不对。我有一次就是键值顺序写反，花了一分钟才排除了这个低级失误。

第三，边界条件：如果k等于不同元素的总数，那整个循环里堆都没超过 k，不会被 pop，最后返回的确实是全部元素，行为正确；但如果nums为空，Counter为空，循环不执行，返回空列表，也符合预期。这两个小边界你可以顺手写在代码注释里，面试时主动提一句，印象分会好很多。

3. 方案二：快速选择（Quick Select）极致优化

3.1 快速选择的思路来源

如果说堆方案是“稳”，那快速选择就是“快”。它借用快速排序里的 partition 思想，但和快排不同的是，快排每次递归都会处理左右两个区间，而快速选择只需要处理“目标元素所在的那一个区间”，所以平均复杂度能做到 O(n)。

我们现在的场景是：有一个字典，里面有 n’ 个键值对，每个键对应一个频率。我想找频率第 k 大的元素。这本质上是一个“顺序统计量”问题，而快速选择就是专门解决这类问题的。

它的过程我用人话描述一遍：随便从所有元素里挑一个基准（pivot），把所有频率比它高的放左边，比它低的放右边。如果基准最终落在下标 k-1 的位置，那左边这些元素（包括基准自己）正好是前 k 个高频元素。如果基准落在了更靠左的位置，说明前 k 个里还有一部分在右边，那我们就去右边继续找；反之去左边继续找。

3.2 partition 实现与关键细节

from collections import Counter import random def top_k_frequent(nums, k): freq_map = Counter(nums) unique_nums = list(freq_map.keys()) n = len(unique_nums) def partition(left, right, pivot_index): pivot_freq = freq_map[unique_nums[pivot_index]] # 把基准先挪到最右边 unique_nums[pivot_index], unique_nums[right] = unique_nums[right], unique_nums[pivot_index] store_index = left for i in range(left, right): if freq_map[unique_nums[i]] > pivot_freq: unique_nums[store_index], unique_nums[i] = unique_nums[i], unique_nums[store_index] store_index += 1 # 把基准放回它正确的位置 unique_nums[store_index], unique_nums[right] = unique_nums[right], unique_nums[store_index] return store_index def quick_select(left, right, k_smallest): if left == right: return [unique_nums[left]] pivot_index = random.randint(left, right) pivot_index = partition(left, right, pivot_index) if pivot_index == k_smallest: return unique_nums[:pivot_index + 1] elif pivot_index < k_smallest: return quick_select(pivot_index + 1, right, k_smallest) else: return quick_select(left, pivot_index - 1, k_smallest) return quick_select(0, n - 1, k - 1)

这里需要重点解释的是 partition 那一步：我用的是“降序排列的 partition”，也就是把频率高的放左边。遍历区间时，凡是遇到频率大于基准的，就把它交换到左侧的 store_index 位置，最后把基准放到 store_index 位置。这样基准左边的所有元素频率都不小于它，右边的都小于它。

还有一个初始化细节：pivot_index = random.randint(left, right)。引入随机化不是多此一举，而是为了规避最坏情况。如果上面没有随机化，而是固定选 left 或者 right，在极端输入下可能会退化到 O(n²)。随机化基准能保证期望复杂度 O(n)。

3.3 平均 O(n)，为什么最坏会退化

快速选择的平均复杂度是 O(n)，证明的逻辑是：每轮 partition 的扫描长度递减，第一轮扫 n，第二轮大约扫 n/2，第三轮大约扫 n/4，加起来是 n + n/2 + n/4 + ... = 2n。但前提是每次 partition 都能把区间大致对半分。如果基准选得很差，比如每次都是最大值或最小值，那每轮只能排除一个元素，总扫描量变成 n + (n-1) + (n-2) + ... = O(n²)。

所以我在实现里特意用random.randint选基准。这也是一种实战经验：面试时你可以先说“思路基于快排 partition”，再补一句“为了避免最坏情况，我们随机选基准，期望复杂度 O(n)”，这能展示你对算法鲁棒性有意识。

3.4 快速选择的适用边界

快速选择虽然快，但它有一个特点：会修改原始数组的顺序。如果题目要求不能修改原数组，或者数组本身就是只读的，你需要把元素先拷贝一份，这会额外增加空间开销。此外，快速选择的结果是“前 k 个元素”，但这 k 个元素内部的顺序是随机的，如果你要求结果必须按频次从高到低返回，还得再排一次，那 O(n) 的优势就没了。

所以在实际面试中，我通常把快速选择作为“进阶优化方案”来提出，而不是第一方案。先用堆方案把正确答案稳稳妥妥地跑通，再等面试官追问“能不能再快一点”时，引出快速选择，这样节奏感最好。

4. 方案三：桶排序——空间换时间的巧解

4.1 桶排序思想本质：用频率做下标

桶排序能在这道题里成立，依赖一个关键规律：数组长度为 n，那么某个元素出现次数的最大值不可能超过 n，最小值至少是 1。这说明“频率”本身是一个范围极其有限的整数，适合做“桶下标”。

具体做法是：先建一个长度为 n+1 的桶数组，下标 i 存储“所有出现次数恰好为 i 的元素”。然后从大下标往小下标遍历桶，经过的每个元素都加到结果里，累计到 k 个就停止。因为每个元素只被访问一次，加上统计频次的遍历，整体时间复杂度 O(n)。

4.2 代码实现解析

from collections import Counter def top_k_frequent(nums, k): freq_map = Counter(nums) # 桶下标为频次，桶大小 n+1 足够 buckets = [[] for _ in range(len(nums) + 1)] for num, freq in freq_map.items(): buckets[freq].append(num) result = [] for freq in range(len(buckets) - 1, 0, -1): for num in buckets[freq]: result.append(num) if len(result) == k: return result return result

这里的buckets = [[] for _ in range(len(nums) + 1)]是容易出错的地方：如果你写成[[]] * (len(nums) + 1)，那所有桶都会指向同一个列表对象，往一个桶 append，其他桶也会跟着变。这个坑我在初学 Python 时踩过不止一次，看到这里的朋友一定要记住：n 个互不干扰的空列表，必须用列表推导式创建。

4.3 O(n) 代价到底是什么

桶排序表面上快得离谱，时间复杂度直接到 O(n)，但代价是空间复杂度也是 O(n)。构建 n+1 个桶，即使某些桶是空的，只要桶结构存在，就占内存。如果 n 是 10 的 6 次方，那么桶数组本身就包含 100 万个空列表，这个内存开销比堆方案大不少。

另外一点，桶排序的时间并不是严格“无常数”的 O(n)。遍历桶时，它是从高到低扫，假设最大频次是 m，那么至少会扫 m 次桶索引。因为 m <= n，所以整体扫描仍然是 O(n)，但如果 k 很小，比如 k=1，堆方案只需要 log k 的代价，其实比桶排序更“划算”。所以选型时不能只看大 O，要看实际数据。

桶排序还有一个隐含好处：它天然支持“频次相同的元素批量输出”。比如某个频次下挂了好几个元素，一次性全可以进结果，不需要像堆那样一个个比较。

5. 三种方案对比与选型决策

5.1 复杂度与适用场景一张表说清楚

5.2 面试中怎么把这道题“讲出层次”

我个人的面试讲法是遵循一个递进逻辑：先承认暴力排序可行，但点出它 O(n log n) 不是最优；然后给出堆优化，解释小顶堆为什么能保持堆大小不超过 k；接着如果面试官追问，再补充桶排序思路，讲清楚它为什么能到 O(n)，以及它的内存代价；最后如果面试官问“你还能压吗”，再抛出快速选择。

这套递进的好处是，它展示了你对“复杂度优化路径”的完整认知，而不是只记得一个答案。我自己作为模拟面试官问别人这道题时，最喜欢听到的回答就是“排序可行，但我们可以用小顶堆把复杂度压到 O(n log k)”，这句话一出来，说明对方真的理解了 Top K 问题的本质。

5.3 变种题与延伸考点

这道题的变种非常多，刷过之后一定要趁热打铁：

• “统计字符串数组中出现频率前 k 的单词”，这个会在频次相同时要求按字典序排序，堆比较规则就得改成(-freq, word)或自定义比较器。
• “数据流中不断进来新元素，实时返回当前前 k 个高频元素”，这是堆方案的动态版，可以用固定大小堆 + 哈希表配合惰性删除实现。
• “找出现频率超过 n/k 的元素”，也就是多数元素问题的推广，可以用摩尔投票变体。
• “二维矩阵中每个元素带权重，求全局 Top K”，本质还是把多维转化成一维键值对处理。

万变不离其宗：只要你建立“统计频次 + 选出 Top K”这个分析框架，后面遇到所有变种都能快速定位考点。

6. 常见问题与实战避坑

6.1 边界条件自查清单

根据我实际跑题的经验，以下这些 case 最好在写完代码后立刻过一遍：

• nums = []：任何方案都应该返回[]，不能抛异常。
• k = 1：堆方案里堆永远只保留一个元素，快速选择只需要一次 partition 即可定位。
• 数组里所有元素都相同，比如[2,2,2,2]，k = 1：桶排序里buckets[4] = [2]，遍历到 freq=4 时直接命中。注意这时候如果k > 1，题目本身可能不合法，但代码仍然不应越界。
• 频次相等但元素不同，比如[1,1,2,2,3,3]，k = 2：三种方案都可能返回任意两个不同的元素，这是被题目允许的，不要在测试时纠结到底该返回 1 和 2 还是 2 和 3。

6.2 Python 实现的几个隐藏陷阱

第一个陷阱是heapq的元组比较。前面提到过，(freq, num)在同频时比较 num，这会让堆在“同频元素之间”做额外的比较操作。如果你追求极致性能，可以用(freq, num)的形式但不要重写比较器，保持简单即可。

第二个陷阱是Counter.most_common(k)。这是 Python 内置一行解，内部实现就是用堆。我在刷题时见过有人直接用：

return [item[0] for item in Counter(nums).most_common(k)]

这个答案完全正确，而且代码极短。但如果你在面试里直接丢这一行，面试官可能会觉得你在调库，而不是真的理解算法。我建议平时练习时先手写堆，面试时如果对方允许“使用标准库”，再用most_common作为代码简化的结尾。

第三个陷阱是桶排序初始化空列表的写法。前面已经强调过，[[]] * n是深坑，一定用[[] for _ in range(n)]。我自己在本地跑的时候，这个 bug 导致结果里出现一堆重复元素，排查了半天才反应过来。

6.3 本地性能实测记录

我在本地用随机数据跑了三种方案，数据规模是生成长度 20 万的数组，元素取值范围 1 到 1000，这样不同元素数量不会太多，频次分布比较自然，k取 10。在同一台开发机上：

• 堆方案耗时大约 0.1 秒级别，已经十分流畅。
• 桶排序比堆略快一点，但差距没有想象中那么大，因为分配 20 万个空桶本身也有内存操作成本。
• 快速选择在这组随机数据上表现和桶排序相当，但由于随机基准的存在，单次运行时间有小幅波动。

这个测试说明一个道理：复杂度的大 O 只是纸面指标，实际常数、内存分配、数据分布都会影响真实耗时。所以面试时讲方案，一定要说“理论上 O(n log k) 和 O(n) 的差距，在 k 比较小或者 n 很大时才明显”，这个判断比记复杂度更重要。

6.4 我遇到过的“莫名其妙”报错

一个比较典型的报错是：快速选择写好之后，return unique_nums[:pivot_index + 1]返回的切片顺序不对，或者边界上差了 1。这个根因是对“第 k 小对应下标 k-1”理解不够扎实。建议你画一画：如果我们要找第 1 大的频率，它在下标 0；第 k 大的频率，它在下标 k-1。所以quick_select的 target 参数是k - 1，递归终止条件是pivot_index == target。

还有一个容易忽视的点：桶排序遍历桶时，如果某个桶的上限频率很大，中间的频率可能是空的，但遍历循环仍然要一路扫下来。比如一个数组里元素最大频次是 10 万，但只有几个频次，那么桶排序会在空桶上花时间。这也是为什么当 k 特别小、最大频次特别高时，堆方案反而是更优选择的原因。

最后再补一个长期经验：如果你使用的是 Python 这类带自动 GC 的语言，处理超大数组时，Counter生成的字典、结果列表、堆结构会同时占用内存，本地跑超大测试时留意一下内存峰值。刷题平台一般限制在几百兆以内，问题不大，但如果你自己用海量数据做压力测试，还是要稍微留心。

拿我自己来说，这道题前后刷了不下五遍，每次重刷都会想通一个新的细节，比如同频元素在堆里谁去谁留、随机化基准为什么能避免退化、桶排序在 k 很小的时候其实没那么香。算法题的乐趣就在这种“一层层往下拆”的过程里。希望这篇拆解能帮你把 347 题的每个坑都提前踩平，面试时无论被追问“为什么用堆”还是“能不能更快”，你都能从容接住。