★ FEATURED ARTICLE 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(), keylambda 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。这说明“频率”本身是一个范围极其有限的整数适合做“桶下标”。具体做法是先建一个长度为 n1 的桶数组下标 i 存储“所有出现次数恰好为 i 的元素”。然后从大下标往小下标遍历桶经过的每个元素都加到结果里累计到 k 个就停止。因为每个元素只被访问一次加上统计频次的遍历整体时间复杂度 O(n)。4.2 代码实现解析from collections import Counter def top_k_frequent(nums, k): freq_map Counter(nums) # 桶下标为频次桶大小 n1 足够 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)。构建 n1 个桶即使某些桶是空的只要桶结构存在就占内存。如果 n 是 10 的 6 次方那么桶数组本身就包含 100 万个空列表这个内存开销比堆方案大不少。另外一点桶排序的时间并不是严格“无常数”的 O(n)。遍历桶时它是从高到低扫假设最大频次是 m那么至少会扫 m 次桶索引。因为 m n所以整体扫描仍然是 O(n)但如果 k 很小比如 k1堆方案只需要 log k 的代价其实比桶排序更“划算”。所以选型时不能只看大 O要看实际数据。桶排序还有一个隐含好处它天然支持“频次相同的元素批量输出”。比如某个频次下挂了好几个元素一次性全可以进结果不需要像堆那样一个个比较。5. 三种方案对比与选型决策5.1 复杂度与适用场景一张表说清楚方案时间复杂度空间复杂度是否稳定排序结果典型适用场景排序暴力法O(n log n)O(n)可以排序输出数据量小图省事哈希 小顶堆O(n log k)O(n)不保证内部排序大多数面试首选k 很小时优势最大快速选择平均 O(n)最坏 O(n²)O(n)不保证内部排序k 很大或接近 n 时可优化到最后一步桶排序O(n)O(n)天然从高频到低频遍历频率范围有限n 可控且内存充足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]遍历到 freq4 时直接命中。注意这时候如果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 题的每个坑都提前踩平面试时无论被追问“为什么用堆”还是“能不能更快”你都能从容接住。
阅读完成 · 觉得有帮助？
