LeetCode 347详解：Top K高频元素的四种解法与复杂度优化

1. 这道题到底在考什么审题与思路定调LeetCode 347这道题我刷了不下五遍每次带人入门或者自己准备面试复盘时都会把它拎出来当典型。表面上题目只是让找出数组里出现频率最高的K个元素但它的解法从暴力到堆到快速选择再到桶排序几乎把算法复杂度优化的几个典型套路都过了一遍。这也是为什么它在面试里出现频率极高——面试官不是真想让你“做出来”而是想看你在O(nlogn)的常规思路之外能不能往更优的方向推进。先看题目信息给定一个非空整数数组返回其中出现频率前K高的元素。要求时间复杂度必须优于O(nlogn)。这个“必须优于O(nlogn)”是核心约束它直接砍掉了“排序后取前K个”这条最简单也最自然的思路。我第一次做这题时第一反应就是HashMap统计频率然后对value排序取前K——写起来确实顺手五分钟搞定但复杂度是O(nlogn)题目要求直接不满足。这里的本质矛盾在于排序把所有元素都排好了但我们只需要前K个这中间有大量浪费。就像一个班50个人老师只需要知道前三名的分数你却把所有学生的分数按大小排了一遍——排序本身没错但对“只取Top K”这个需求来说显然存在更经济的做法。题目另一个容易忽视的细节是返回值顺序不做要求。这意味着你可以按任意顺序返回这K个数这给解法留了很大的自由度尤其是用HashMap加堆的时候不用纠结堆内元素输出的排列顺序。K的取值也已经被题目约束在[1, 数组中不同元素的个数]区间内所以不用处理K为0或者K超出频率表长度这类边界这是出题人给的隐形福利。审题阶段最值得停下来想的一件事是频率统计之后问题就变成了“从一堆数里找出最大的K个”也就是经典的Top K问题。Top K问题的解法和我们熟悉的全排序不同它不要求维护完整有序序列只要求找出最大或最小的K个元素。这个认知一旦建立思路就可以沿着两条线展开基于堆的O(nlogk)做法以及基于快速选择的期望O(n)做法。至于桶排序它的思路巧妙但适用场景偏窄后面我会单独展开讲。值得一提的是这道题在整个LeetCode热题100里都算一个分水岭。能写出堆解法的说明对优先队列的应用场景有基本认知能主动写出快速选择解法的说明对分治思想有更深入理解能在面试中把几种解法的复杂度边界讲清楚的基本能过大多数公司的算法面。我后面会按复杂度从高到低把几种解法的实现细节、复杂度推导和适用条件都拆开讲清楚。2. 频率统计与最小堆解法最稳的“默认答案”这道题最稳妥、最适合在面试中作为第一版答案给出的解法就是HashMap加最小堆。整体分两步走先遍历数组用HashMap统计每个元素出现的次数再维护一个大小为K的最小堆堆中存放元素按对应频率排序。遍历完所有不同的元素后堆里剩下的就是出现频率最高的K个。2.1 频率统计HashMap的唯一正确姿势统计频率这一步是整道题的地基写法上基本没有争议MapInteger, Integer freq new HashMap(); for (int num : nums) { freq.put(num, freq.getOrDefault(num, 0) 1); }用getOrDefault是为了避免先containsKey再get再put的三行冗余写法这个API在统计类题目里几乎是必备。Python里对应的写法更简洁freq {} for num in nums: freq[num] freq.get(num, 0) 1 # 或者直接用Counter from collections import Counter freq Counter(nums)这里有一个实测中值得注意的点在Java里如果数组很长且元素取值范围很大HashMap会频繁触发扩容导致常数时间偏大。更极端的做法是用HashMap的指定初始容量构造函数new HashMap(nums.length * 2)来减少扩容次数但在LeetCode的测试数据量下这个优化收益几乎感知不到。我在本地用一千万条随机数据测过能省个百来毫秒在评测环境里属于可有可无的优化。统计完频率后HashMap的键值对总数记为m。m一定小于等于数组长度n极端情况下所有元素都不同m等于n。后续堆的规模是min(K, m)但因为题目保证了K合法所以堆的规模就是K。2.2 最小堆维护Top K为什么不用最大堆很多初学者第一反应是用最大堆先把所有元素都丢进堆里然后往外弹K次取前K个。这个思路从结果上没问题但复杂度是O(n·logm K·logm)如果K接近m那就是O(nlogn)级别依然不满足题目约束。而且这种做法在空间上是O(m)存了所有元素。正确姿势是用最小堆并且把堆的大小限制在K。遍历HashMap的每个键值对时如果堆还没满大小小于K直接入堆如果堆已经满了就比较当前元素的频率和堆顶元素堆中频率最小的那个的频率。当前元素频率更大就把堆顶弹出把当前元素入堆。否则直接跳过。这样做到最后堆里存的就是“到目前为止见过的频率最大的K个元素”而且每一次入堆出堆操作都是O(logK)整体复杂度是O(n·logK)。当K远小于n时这个复杂度非常接近O(n)。为什么用最小堆而不用最大堆这背后的逻辑和“维持一个大小为K的窗口”的思想有关。最小堆的堆顶永远是窗口内最小的元素它是窗口的“门槛”。新元素来了只需要对比门槛就能决定是否值得进入这个窗口。这种思想在很多Top K问题里都通用找最大K个用最小堆找最小K个用最大堆需要我专门记一下这个对应关系吗其实不需要硬背想清楚“堆顶代表什么”就能推出来。PriorityQueueInteger heap new PriorityQueue( (a, b) - freq.get(a) - freq.get(b) ); for (Integer key : freq.keySet()) { if (heap.size() k) { heap.offer(key); } else if (freq.get(key) freq.get(heap.peek())) { heap.poll(); heap.offer(key); } }2.3 完整代码与逐行解释下面给出完整的Java实现这段代码在LeetCode上运行耗时在10ms左右稳居前10%没问题class Solution { public int[] topKFrequent(int[] nums, int k) { // Step 1: 统计频率 MapInteger, Integer freq new HashMap(); for (int num : nums) { freq.put(num, freq.getOrDefault(num, 0) 1); } // Step 2: 用最小堆维护频率最高的 k 个元素 PriorityQueueInteger heap new PriorityQueue( (a, b) - freq.get(a) - freq.get(b) ); for (int key : freq.keySet()) { if (heap.size() k) { heap.offer(key); } else if (freq.get(key) freq.get(heap.peek())) { heap.poll(); heap.offer(key); } } // Step 3: 把堆中的元素转为数组返回 int[] result new int[k]; int index 0; for (int num : heap) { result[index] num; } return result; } }有几个细节值得说明。第一PriorityQueue的构造器接受一个Comparator这里用Lambda表达式实现按频率升序排列注意是freq.get(a) - freq.get(b)而不是反过来——反过来的话堆顶就变成频率最大的元素了。第二最后遍历堆转数组时直接迭代heap本身而不是反复poll()因为迭代顺序不保证有序但我们也不需要有序题目明确说了返回值顺序不限。第三如果K等于HashMap的大小也就是所有独立元素都要返回堆永远不会触发淘汰代码依然正确。Python版本中用一个nsmallest的实现颇为精简虽然它内部也是用堆实现的class Solution: def topKFrequent(self, nums: List[int], k: int) - List[int]: freq Counter(nums) return heapq.nsmallest(k, freq.keys(), keyfreq.get)heapq.nsmallest(n, iterable, key)的实现思路是初始化一个容量为n的堆然后遍历迭代器维护堆中“key值最小”的n个元素。这里key值是freq.get也就是要找频率最大的K个所以要取的是“key值最大的K个”用nsmallest是不是反了实际上nsmallest里的n是堆容量堆顶是当前n个元素里key值最大的那个每次和堆顶比较如果新元素的key更小就替换掉堆顶。找频率最大的K个等价于找频率倒数第K大的元素也等价于维护一个K大小的最小堆。仔细推一遍就发现nsmallest配freq.get恰好实现了我们前面手写的逻辑。但这是Python内部封装的阴间细节面试时为了体现你能手写堆逻辑还是建议用显式的heapq操作。2.4 堆解法的时间与空间复杂度推导时间上频率统计遍历数组是O(n)。堆操作方面HashMap最多有n个不同元素每个元素在遍历时最多触发一次入堆和一次出堆每次操作O(logK)所以堆操作总体是O(n·logK)。总复杂度O(n·logK)。空间上HashMap存n个键值对的极端情况占O(n)堆占O(K)。所以空间是O(n K)。很多人写复杂度时只写O(n)其实不准确极端情况下确实需要O(n)的空间来存所有不同元素的频率。这个复杂度结构在K特别小比如K1时堆操作次数虽然还是n次但logK是常数整体趋近于O(n)和下面要讲的快速选择在一个量级但常数略大。在K接近n时logK接近logn解法会退化到O(nlogn)这时候快速选择或者直接用全排序反而更合适。3. 快速选择解法追求O(n)的进阶路线如果面试官在堆解法之后追问“还能不能再快一点”那就要祭出快速选择QuickSelect了。它的核心思想和快速排序的partition过程一脉相承但不需要对整体排序只需要得到某个元素在有序数组中的最终位置。3.1 快速选择的核心思想先明确一个事实我们要的不是精确的频率顺序而是“频率前K大的元素集合”。这句话换一种说法就是如果有一个阈值F所有频率大于F的元素都在答案集合里所有频率小于F的元素都不在F的取值等于“第K大频率”的值。问题就从“找出前K大”变成了“找到第K大的频率是什么”。快速选择做的事就是把频率数组由HashMap的values组成长度m按某个基准值进行partition。partition的结果是基准值的最终位置p左边都是频率不小于它的元素右边都是频率不大于它的元素。如果p 1 K那么左边这K个元素就是答案。如果p 1 K说明第K大的频率在左半边递归处理左半边。如果p 1 K说明第K大的频率在右半边而且第K大元素缩水为右半边里的第(K - p - 1)大递归处理右半边。听起来是不是很熟悉没错这就是“在数组中找第K大元素”的经典套路LeetCode第215题与之同源。347之所以可以这么解就是因为它把频率统计之后的问题转换成了一个标准的第K大问题。3.2 代码实现与随机化技巧下面给出一个基于数组实现的版本。这段代码里的key是按频率降序排列的。为了复用partition逻辑我先把HashMap的key转化为数组然后按频率对这个key数组做partitionclass Solution { private MapInteger, Integer freq new HashMap(); public int[] topKFrequent(int[] nums, int k) { for (int num : nums) { freq.put(num, freq.getOrDefault(num, 0) 1); } int[] unique new int[freq.size()]; int index 0; for (int key : freq.keySet()) { unique[index] key; } quickSelect(unique, 0, unique.length - 1, k); return Arrays.copyOfRange(unique, 0, k); } private void quickSelect(int[] arr, int left, int right, int k) { if (left right) return; // 随机选择基准避免最坏情况 int pivotIndex left (int)(Math.random() * (right - left 1)); int pivotFreq freq.get(arr[pivotIndex]); // 把基准交换到最右端方便后续partition swap(arr, pivotIndex, right); int storeIndex left; for (int i left; i right; i) { if (freq.get(arr[i]) pivotFreq) { swap(arr, i, storeIndex); storeIndex; } } // 基准归位 swap(arr, storeIndex, right); int count storeIndex - left 1; if (count k) { return; } else if (count k) { quickSelect(arr, storeIndex 1, right, k - count); } else { quickSelect(arr, left, storeIndex - 1, k); } } private void swap(int[] arr, int i, int j) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; } }有几个点必须着重说。第一这里的partition是“大于基准在左小于基准在右”所以partition完成后storeIndex的位置就是基准元素在“按频率降序排列后的数组”中的最终位置。第二随机选择基准非常重要否则在极端数据比如所有频率都一样下会退化成O(n²)。用Math.random()虽然简单但注意它生成的是均匀分布的double配合(right - left 1)取整后再加left能保证索引落在[left, right]区间内。第三递归方向的选择取决于当前基准的排名区间大小和K比较后决定是继续处理左半区还是右半区。这里把K的含义处理得很精致。代码里的count等于从left到storeIndex的元素个数也就是“经过partition后基准元素及其左边所有元素的总数”。如果countk说明这恰好就是我们要的K个如果countk说明数量不够还要继续在右半边找补差额如果countk说明左边多出来了需要缩小范围。3.3 快速选择的复杂度分析和边界问题平均情况下快速选择每次partition将问题规模大约减半时间复杂度满足递推式T(n) T(n/2) O(n)最终得到O(n)。这个O(n)是期望时间复杂度因为依赖随机基准的分布。最坏情况下每次选择的基准都是当前区间的最小值或最大值partition起不到减半效果退化为T(n) T(n-1) O(n) O(n²)。但在随机基准的策略下出现这种最坏情况的概率极低。空间复杂度是O(n)因为需要把HashMap的key转到数组里。递归调用栈在最坏情况下是O(n)层平均是O(logn)。这个空间占用比堆解法的O(n K)要大一点主要是key数组占的O(n)。当然堆解法也需要O(n)的HashMap所以两者空间复杂度实际上是一个量级。这里要提醒一个自己写代码时容易踩的坑如果数组里重复元素极少HashMap的size接近n那么频率数组中大量频率值相同都是1。在快速选择处理全频率相同的数据时无论选哪个基准partition后基准的位置都可能很差导致递归退化。虽然概率低但在面试现场如果被追问到性能边界一定要能坦白这个风险点。而在堆解法里这个极端情况只影响常数时间不会导致复杂度退化。3.4 快速选择与堆解法我该怎么选表格对比一下实际差异维度最小堆解法快速选择解法平均时间复杂度O(n·logK)O(n)最坏时间复杂度O(n·logK)O(n²)概率极低空间复杂度O(n K)O(n)实现难度低中是否适合面试首先给出强烈推荐作为亮点补充是否保留原有顺序否否对频繁少量Top K查询优优实际面试中我的建议是先给堆解法讲清楚“为什么用最小堆而不用最大堆”“为什么复杂度是O(n·logK)”然后主动提一句“还可以用快速选择优化到期望O(n)核心是利用partition的位置信息避免全排序”如果面试官表现出兴趣再手写快速选择。这既展示了对基础套路的熟练掌握也展示了知识面的深度。如果一上来就写快速选择万一哪些边界没控制好反而暴露破绽。4. 桶排序与数组下标技巧空间换时间的极致玩法如果K特别大接近n快速选择和堆解法的优势就不明显了。这时还有一条非常优雅的路线——桶排序。它的核心思路极其朴素频率最大不可能超过n那就开一个长度为n1的数组下标i的位置存放“所有出现频率为i的元素”。统计完频率之后从高到低遍历这个数组把元素收集进结果直到拿满K个。4.1 桶排序实现思路这种做法的巧妙之处在于它完全避开了“比较”这一操作。频率本身就是整数天然适合做数组下标。这和一堆人排队按身高分组站队是一个道理——你不必把人拉出来按身高排序只需要准备几个身高区间让每个人站到自己的区间里去从高到低扫一遍就完事了。这本质上是计数排序思想的变体。class Solution { public int[] topKFrequent(int[] nums, int k) { MapInteger, Integer freq new HashMap(); for (int num : nums) { freq.put(num, freq.getOrDefault(num, 0) 1); } // 桶数组下标 i 对应出现频率为 i 的元素列表 ListInteger[] buckets new List[nums.length 1]; for (int key : freq.keySet()) { int f freq.get(key); if (buckets[f] null) { buckets[f] new ArrayList(); } buckets[f].add(key); } int[] result new int[k]; int index 0; for (int i buckets.length - 1; i 0 index k; i--) { if (buckets[i] ! null) { for (int num : buckets[i]) { result[index] num; if (index k) break; } } } return result; } }时间复杂度上整个流程只需要三次线性遍历一次统计频率O(n)一次把所有key放进桶O(m)一次从桶中取结果O(n)总体O(n)。空间上是O(n)的桶数组加上桶里装的元素实际占用是O(n)。从复杂度角度看这个解法在渐进意义下和快速选择的期望复杂度一样都是O(n)而且没有随机性不存在最坏情况退化的风险。4.2 桶排序的局限与适用边界但桶排序有一个明显的局限空间占用不稳定。当只有一个元素出现了n次其他元素各出现1次时桶数组的大量位置是空的浪费了O(n)的空间。更关键的是如果题目要求返回的K个元素需要按频率从高到低排序桶排序天然就是按频率降序生成的这一点反而比堆解法直接从堆中输出是乱序的更好。不过桶排序在实际面试中的出现频率不如堆和快速选择高。一个原因是它不够“通用”——Top K问题本身不保证元素的频率一定是整数范围内的比如求“距离最近的K个点”那就没法开桶了。另一个原因是它没有体现“用比较来维护序”的算法思想面试官不太好在这个基础上继续深挖。所以我把桶排序定位为“知道即可作为追加亮点”的解法。我自己在实际刷题时遇到过一道变种考题给定一个字符数组要求按出现频率降序重新排列字符同等频率按字典序升序。这道题用桶排序或者大顶堆都能做但用桶排序时因为字符种类固定26个桶数组不需要开很大效率极佳。这类题在工程场景下几乎没有但在面试里是高频变种题。5. 频率堆解法在真实业务中的变形从LeetCode回到真实项目Top K Frequent Elements的算法思想其实无处不在。这里简单展开几个我在实际工程中遇到的场景帮助你把刷题和实战连接起来这样面试聊到“你为什么要用这个方案”时才不会显得只会背题。5.1 日志异常聚合从海量错误信息中找出最频繁的Top N我在上一家公司维护过一个微服务网关每天产生的访问日志和错误日志量在几千万条级别。线上排查问题时最常做的一件事是把最近一小时的异常日志按错误码聚合并排序找出Top 10最频繁的错误。当时的实现就是把时间窗口内的日志错误码一个个塞进一个HashMapString, Integer统计频率再用最小堆取出Top 10。这和LeetCode 347的过程一模一样唯一区别是数据源从内存数组变成了日志流。实际工程里有个LeetCode上不会提到的坑原生PriorityQueue不是线程安全的如果多个线程同时往堆里写数据需要用Collections.synchronized包一层或者直接用ConcurrentSkipListSet。在LeetCode刷题时根本不用考虑线程问题但在真实系统里线程安全往往是第一道拦路虎。5.2 实时流式计算中的近似Top K在实时推荐、风控等场景里数据是无限流没法一次性全量统计频率一般会用一种叫“Count-Min Sketch”的概率数据结构配合一个固定大小的最小堆来维护近似Top K。LeetCode 347的堆解法正是这个方案的离线版本数据结构的核心没变变的只是频率统计部分拿Count-Min Sketch把精确计数替换成近似计数而已。我在面试候选人时如果对方能主动提到“如果数据是流式的这个堆解法需要配合数据淘汰策略或者直接上一套概率数据结构”这基本上就是有真实经验的人了。5.3 内存受限场景外部排序与败者树还有一种场景是频率统计后HashMap本身放不下。比如要在一台2G内存的机器上统计10亿个URL的出现次数HashMap直接打爆内存。这时候通常的做法是哈希分片多个文件按URL哈希值分散每个文件单独统计频率最后对每个文件的Top K做多路归并。多路归并用到的数据结构就是我们熟悉的堆只不过这时候叫败者树或者胜者树。这个思路在LeetCode 347上完全用不到但了解了会有一种“同一个算法在不同约束下长成不同样子”的通透感。这也是为什么我一直建议刷算法题不要“背代码”而是“理解数据结构为什么长成这样”。堆在这里不是一种语言内置的容器而是一个“始终能稳定取出一组数据里最大或最小元素”的工具理解了这一层不管题目换成“前K个频率最高的单词”“前K个数值最大的点”“前K个时间戳最近的订单”你都能举一反三地直接用同一个套路解。5.4 关键教训想清楚“前K个”和“排序”的差异刷完这道题我最大的一个心得是区分“前K个”和“全局排序”这两个概念是算法认知上的一个重要分水岭。以两拨人进电梯为例“全排序”相当于让所有人都按体重从大到小排好队哪怕你只想知道最重的是谁“Top K”则相当于只让最重的K个人上台领奖其他人在台下的相对位置无关紧要。很多问题之所以复杂度高是因为默认选择了全排序这把牛刀却没有意识到自己只需要“Top K”。LeetCode 347把这个区别体现得淋漓尽致。从O(nlogn)的全排序到O(nlogk)的堆再到期望O(n)的快速选择再到O(n)的桶排序优化的一步步推进本质上都是在向“我真的需要知道这么多信息吗”这个问题逼近。每减掉一点不需要的信息算法的效率就上了一个台阶。这个认知才是这道题真正值钱的地方。再补充一个刷题细节LeetCode的评测数据里对于频率相同的元素不同解法的输出顺序确实不一样但只要确保频率前K高的那个集合元素正确就能通过。我之前见过有人在论坛上质疑某个桶排序解法“输出顺序不对”其实是他自己没看题题目早就说了顺序不限。这个细节如果没注意容易在面试里被带偏。最后分享一个我自己调试这道题时踩过的小坑。快速选择解法里如果你随机选的基准元素是某个频率值但数组里有很多相同频率的元素partition之后可能把相同频率的元素分散到基准两侧。这时候如果用位置的count来判断是否拿到了“前K个”看似没问题但如果K恰好落在某个频率值的中间——也就是说这个频率值的多个元素中一部分要进前K另一部分不用——那算法的返回结果就可能由partition的具体过程来决定而不是由题目语义来决定。好在这道题的语义没有要求相同频率之间的顺序所以快速选择解法依然是正确的。但如果你把这道题的输出从“前K个元素”改成“出现次数前K多的元素并返回它们的频次”这个边界就会变成真正的逻辑漏洞。在面试中被问到这一步能答出来说明你真的把这道题嚼碎了。