高频算法题347：前K个高频元素的四种解法与面试套路

如果你刷过一段时间算法题大概率会撞上 347 这道题“前 K 个高频元素”。题目很短解法也不少但我见过太多人在面试里把它写岔有人一上来就排序忘了统计频次有人用大顶堆维护全部元素复杂度直接拉满还有人在边界条件上翻车K 等于数组长度时数组越界。这道题之所以高频是因为它把哈希表、堆、快速选择、桶排序全部串在了一个小问题上而且面试官稍微一追问就能延伸到数据流、海量数据这些底层场景。今天我就从刷题和面试两个角度把它拆开揉碎讲清楚顺便把那些不写在题解里的坑都摊开说。1. 题目解读与思路总览1.1 题目到底在考什么先看清题意给定一个整数数组nums和一个整数k要返回数组中出现频率最高的前k个元素。注意两点第一返回的是元素本身不是频次第二顺序不重要题目并没有要求按频次降序排列。这意味着你可以用任何顺序返回只要集合正确即可。这一点很多人会忽略白白在返回前做了一步多余的排序。题目背后考察的是两个基础能力一是“统计频次”这个动作能不能想到用哈希表去完成二是“从一堆频次中挑出 Top K”这个动作能不能根据数据规模选择合适的算法。前者几乎是固定答案后者才是拉开差距的地方。数组里元素范围没有限制可能是负数也可能非常大所以不能用固定大小的计数数组必须用哈希表做“元素 - 频次”的映射。举个例子nums [1, 1, 1, 2, 2, 3], k 2应该返回[1, 2]。但如果题目把k改成3那就三个元素都要返回。这个朴素的例子背后藏着各种方法的适用边界下面逐个展开。1.2 五种思路的选型逻辑针对“前 K 个高频元素”常见解法大概有五种全排序、大顶堆、小顶堆、快速选择、桶排序。它们的核心区别在“挑 Top K”这一步。最直观的是把所有不同元素按照频次降序排序然后取前 K 个。这种方法时间复杂度 O(N log N)胜在简单但在数据量大的时候并不划算。大顶堆的思路是把每个元素和频次都丢进堆里最后从堆顶弹出 K 次。堆里维护的是全部 N 个不同元素所以建堆 O(N)弹出 K 次 O(K log N)整体接近 O(N K log N)。问题是空间 O(N)而且在 K 很小的时候维护整个堆属于“杀鸡用牛刀”。小顶堆的思路则是反过来只维护一个大小为 K 的堆堆顶是当前候选里频次最小的那个。每来一个新元素如果频次比堆顶大就替换堆顶。最终堆里剩下的就是前 K 个高频元素。时间复杂度 O(N log K)空间 O(K)。这是在面试中最推荐、也最容易被追问的方案因为它能顺滑地迁移到“数据流”场景。快速选择不走堆而是借鉴快排的 partition 思想在平均 O(N) 时间内找到第 K 大频次的位置然后直接切出前 K 个。缺点是最坏情况退化到 O(N^2)需要用随机化来兜底。桶排序则是把频次当作索引从高频往低频遍历时间复杂度 O(N)但空间也是 O(N)。下面我按“必须先做的统计频次 - 堆方案 - 进阶方案 - 踩坑实录”的顺序讲尽量让你看完就能动手写。2. 哈希表统计频次一切方案的基石2.1 用 Python、C 统计频次的典型写法无论后续选哪种策略第一步永远是统计每个元素的出现次数。这一步最直白也最容易出 bug。Python 里我首选collections.Counterfrom collections import Counter nums [1, 1, 1, 2, 2, 3] counter Counter(nums) # counter {1: 3, 2: 2, 3: 1}Counter本质上就是字典底层是哈希表Counter(nums)内部会遍历数组对每个元素执行一次dict[key] 1时间复杂度 O(N)。如果你不用Counter手写也一样cnt {} for num in nums: cnt[num] cnt.get(num, 0) 1注意cnt.get(num, 0)这一步如果键不存在返回默认值 0避免抛 KeyError。这个写法看起来简单但它隐含了一个细节对字典做get和赋值是 O(1) 平均操作所以整个统计过程是线性的。C 里我通常用unordered_mapunordered_mapint, int cnt; for (int x : nums) { cnt[x]; }unordered_map平均插入和查询也是 O(1)。需要注意虽然这里写法只有三行但背后会涉及哈希冲突处理、扩容面试时你可以提一句“平均 O(1)最坏 O(N)”显得你对底层有了解。2.2 为什么统计频次是绕不开的一步有些新手会想能不能不统计直接在一次遍历中维护一个“滑动窗口”不行因为数组顺序和元素频次无关你没有先验信息就无法判断某个元素是不是最终会排进前 K。举个极端例子nums前面全是 1后面全是 2但 1 出现 100 次2 出现 200 次。不统计完整段数组你不知道 1 和 2 谁才是第一。统计完成后我们需要的数据结构变成了一组(元素, 频次)对。在 Python 里可以用counter.items()拿到C 里则遍历unordered_map。这里有一个值得注意的坑items()的顺序是随机的与元素在数组中的出现先后没有任何关系后续堆或快排只依赖频次不依赖这个顺序所以没问题。统计阶段还有一个冷门边界nums为空数组时counter为空如果k 0要直接返回空列表如果k大于不同元素个数题目通常会保证合法但工程上还是要防御一下否则接下来堆初始化或快排下标会越界。3. 堆方案面试最稳的记忆点与方法论3.1 大顶堆 vs 小顶堆核心取舍必须清楚堆方案最容易混淆的地方就是用大顶堆还是小顶堆。一句话解释如果你要把所有元素都放进堆那就用大顶堆最后弹 K 次如果你只想保留 K 个候选那必须用小顶堆因为堆顶是候选里最弱的新来的强者才能把它顶掉。大顶堆版本的时间复杂度是 O(N K log N)空间 O(N)。对于 N 很大的场景这个空间占用不够好。更重要的是面试官通常会追问“如果 nums 是一个不断到来的数据流没法一次性统计完怎么办”这时候大顶堆没法增量维护而小顶堆天然适合每来一个元素更新它的频次然后判断要不要替换堆顶。所以强烈建议你默认掌握小顶堆维护大小为 K 的方案。它也是这道题在《剑指 Offer》和 LeetCode 讨论区里最主流的“标准答案”。3.2 小顶堆代码逐行拆解先看 Python 版本import heapq from collections import Counter def topKFrequent(nums, k): counter Counter(nums) heap [] for num, freq in counter.items(): if len(heap) k: # 堆未满直接入堆元素顺序是 (freq, num) heapq.heappush(heap, (freq, num)) elif freq heap[0][0]: # 新频次比堆顶大则替换堆顶 heapq.heapreplace(heap, (freq, num)) return [num for _, num in heap]这里有几个细节我要重点说明。第一heapq是 Python 默认的最小堆所以heap[0]是堆中元组里freq最小的那个。我们把(freq, num)放进堆比较时先比较freq如果freq相同再比较num这没问题因为堆中不可能出现两个完全相同的元素属于同频不同值num的比较只是为了让堆结构稳定。第二heapq.heapreplace等价于“先 pop 堆顶再 push 新元素”比分开调用heappopheappush更高效。但要注意它只在堆非空时使用我们前面已经保证了len(heap) k而k 1所以安全。第三最后返回时直接取堆中所有元素的num顺序是堆序不是按频次降序。题目不要求排序所以这样没问题。如果你强迫症犯了非想按频次从高到低输出可以在最后加一步排序但时间复杂度会多一个 O(K log K)不划算。再看 C 版本class Solution { public: vectorint topKFrequent(vectorint nums, int k) { unordered_mapint, int cnt; for (int x : nums) cnt[x]; auto cmp [](const pairint,int a, const pairint,int b) { return a.second b.second; // 频次小顶堆 }; priority_queuepairint,int, vectorpairint,int, decltype(cmp) pq(cmp); for (auto p : cnt) { pq.emplace(p.first, p.second); if (pq.size() k) pq.pop(); } vectorint res; while (!pq.empty()) { res.push_back(pq.top().first); pq.pop(); } return res; } };注意priority_queue默认是大顶堆所以比较器里要让“频次小的优先级高”。用 lambda 自定义比较器时priority_queue的模板参数需要传decltype(cmp)这个写法和常规的排序比较器方向相反特别容易记反。我自己的记忆技巧是priority_queue的 top 是“最后一个被比较函数判定为最应该出队的元素”小顶堆意味着“频次更小的认为更小但 priority_queue 把最大按比较器定义的放顶部所以比较器要返回 a.second b.second 才让最小频次在 top”。如果这个逻辑绕脑子干脆直接用greaterpairint,intpriority_queuepairint,int, vectorpairint,int, greaterpairint,int pq;greater会先按 first 比较所以我们需要把(freq, num)入堆。这也是一种更省心的写法。再次强调pair的默认比较是先 first 后 second所以存(freq, num)时频次是主键。3.3 时间复杂度为什么是 O(N log K)这一步推演面试官可能会让你现场口算。统计频次要遍历整个数组耗时 O(N)。假设数组里不同元素个数为 M一般 M N。接下来对 M 个(num, freq)逐一执行堆操作。堆大小固定为 K入堆和替换堆顶的时间复杂度都是 O(log K)因为有 log K 层需要调整。因此最坏情况下每个不同的元素都要做一次插入或替换操作总复杂度是 O(M log K)。由于 M N所以整体是 O(N log K)。如果 K 远小于 N这个复杂度非常接近线性如果 K 接近 N堆的复杂度会退化成 O(N log N)这时候反而可以考虑快速选择或排序。有一层隐藏细节对每个元素做if freq heap[0][0]的判断是 O(1)只有满足条件才替换。所以实际运行中不是每个元素都会触发堆调整这个常数优化在数据分布不均匀时很可观。比如只有少数元素高频其他都是低频堆被替换的次数会远小于 M。4. 比堆更快的进阶方案快速选择与桶排序4.1 快速选择的原理与代码实现如果面试官说“数据量很大K 也很大堆的 O(N log K) 还是不够快”你就要能接住快速选择。快速选择的本质是我们不需要把全数组有序只需要找到第 K 大频次的位置让左边都是频次大于等于它的元素。这跟快速排序里的 partition 完全一样。Python 实现import random from collections import Counter def topKFrequent(nums, k): cnt Counter(nums) items list(cnt.items()) # [(num, freq)] def partition(left, right): # 随机选择 pivot 下标避免有序输入的退化 pivot_idx random.randint(left, right) items[right], items[pivot_idx] items[pivot_idx], items[right] pivot_freq items[right][1] i left - 1 for j in range(left, right): if items[j][1] pivot_freq: i 1 items[i], items[j] items[j], items[i] items[i 1], items[right] items[right], items[i 1] return i 1 def quick_select(left, right, k_largest): # 在 items[left..right] 中找第 k_largest 大1-based if left right: return left p partition(left, right) left_count p - left 1 if k_largest left_count: return quick_select(left, p - 1, k_largest) elif k_largest left_count: return quick_select(p 1, right, k_largest - left_count) else: return p pos quick_select(0, len(items) - 1, k) return [num for num, _ in items[:pos 1]]这段代码里最容易被忽略的是 partition 的边界。我们随机选择一个 pivot 频次扫一遍把大于等于 pivot 频次的元素都放到左边小于的放到右边。这样 partition 返回的位置 p 左侧所有元素的频次都大于等于右侧。left_count p - left 1表示从 left 到 p 一共有多少个元素这也就是当前区间内“最大的一批”的个数。如果 k_largest 小于 left_count说明第 k 大的目标在左边如果大于说明在右边并且右边要找的位数要减去 left_count。这个逻辑可以画三个小数组验证一下千万别死记代码。快速选择的平均复杂度是 O(N)因为每次 partition 大约把区间减半递推式 T(N) T(N/2) O(N)结果是 O(N)。但最坏情况下如果每次随机都选中最大或最小频次区间只缩小 1复杂度退化为 O(N^2)。随机选 pivot 就是为了让这种情况的概率低到可以忽略。面试时主动说出“我用随机化避免最坏情况”是一个加分项。4.2 桶排序用空间换时间的极端场景桶排序的思想更偏技巧既然最大频次不超过数组长度 N我就可以开一个长度为 N1 的数组下标表示频次值是该频次对应的元素列表。然后从高到低遍历下标收集元素凑够 K 个就返回。Python 实现from collections import Counter def topKFrequent(nums, k): cnt Counter(nums) bucket [[] for _ in range(len(nums) 1)] for num, freq in cnt.items(): bucket[freq].append(num) res [] for freq in range(len(bucket) - 1, 0, -1): for num in bucket[freq]: res.append(num) if len(res) k: return res return res这段代码的时间复杂度是 O(N)因为每个元素入桶一次、出桶一次都是常数操作。空间复杂度也是 O(N)用于存储 bucket 数组和桶内元素列表。桶排序的适用场景是nums长度可接受并且元素频次分布比较集中时桶列表不会特别空。但如果数组有 10 万个元素却只有 3 个不同元素频次最大的桶是 50000中间很多桶是空的for 循环从高频往低频扫也很快因为空桶直接跳过所以还是 O(N)。真正的缺点是需要额外 O(N) 空间并且无法增量处理数据流。如果面试官限定只能用一个堆的额外空间桶排序就不适用。4.3 三种核心方法横向对比方案时间复杂度空间复杂度核心优势主要限制小顶堆O(N log K)O(K)支持数据流、实现简单需要 log K 维护成本快速选择平均 O(N)最坏 O(N²)O(M)M 为不同元素数常数小适合大 K最坏情况需随机化兜底桶排序O(N)O(N)线性时间代码直观需要知道频次上界空间占用较大如果是面试我个人建议先答小顶堆因为这个方案工程上最稳代码不会出错还能顺手接住数据流追问。如果面试官继续问“能不能 O(N)”再展示快速选择或桶排序。这样既有层次又不会在第一时间暴露复杂实现里的边界问题。5. 笔试现场与真实案例中的高频坑5.1 我看过的翻车现场边界条件与比较器这道题在牛客、LeetCode 讨论区和我的日常 code review 里出现的频率超高我复盘过不少错误总离不这几类。第一类是忘记处理“不同元素数小于 k”的情况。虽然题目一般保证 k 合法但在封装函数或线上笔试时防御性判断很重要如果len(cnt) k直接返回所有键即可。否则堆方案在堆没满时就提前开始比较会漏掉高频元素。第二类是 C 比较器方向写反。priority_queue的自定义比较器里return a b代表小顶堆很多从 Java 转 C 的人会习惯性写成return a b结果变成大顶堆堆里永远只装得下频次最大的那个K 1 时直接全错。我的建议是新手上手别用自定义比较器直接pair加greater把频次放 first能省掉 90% 的脑细胞。第三类是快速选择 partition 里用而不是。如果允许等于 pivot 的元素放在右侧那么当大量元素频次相等时left_count可能会小于实际“前 K 大”的个数导致返回的集合不完整。用可以保证所有相等的频次都靠左聚拢但这会带来额外的不稳定性每次 partition 后左侧大小可能略大于理论值不过我们递归时用的是left_count来决定去哪一侧不会出错。第四类是自以为“返回前 K 个高频元素”要求有序在堆完成后又对结果做了一次完整排序。题目没说有序你就不要做多余操作。如果你确实要按频次排序应该在代码里单独说明“这是为了满足输出要求”否则面试官会误以为你没审题。5.2 面试官追问数据流场景怎么快速回答这是 347 题最经典的延伸问题。原题给的是完整数组但如果数据是一个持续到达的流比如用户点击日志你不能先存下来再统计那就必须用小顶堆方案维护当前的 Top K。做法是维护一个哈希表记录每个元素的累计频次同时维护大小为 K 的小顶堆。每个数据到达时更新哈希表频次如果该元素已经在堆中堆可能需要重建这是一个麻烦点如果不在堆中且堆未满直接入堆如果不在堆中且堆已满比较新元素频次和堆顶频次如果大于堆顶则替换。这里有个隐藏问题元素频次是动态增加的已经入堆的元素频次会不断变化但堆中的元素顺序不会自动更新。怎么处理标准做法是“惰性删除”堆内存(freq, num)当元素频次增长时把新的记录入堆同时用一个计数器记录旧记录的有效性弹出时如果堆顶条目的频次不是最新频次就丢弃并重新弹出。这样堆的大小可能超过 K但每个元素最多入堆一次整体摊还复杂度仍然可控。面试时能答出“在堆里存的是历史快照用哈希表校验最新频次”已经很出彩了。还有一种追问是如果内存不足以放下所有不同的元素怎么办那就要引入外部排序、采样估计等思路比如基于分桶的近似 Top K 算法。这部分通常不是算法面试的重点能点到即可不需要展开实现。5.3 从这道题抽象出的通用解题套路347 这道题刷完你可以把它当成一个“套路模板”来记忆。凡是遇到“求前 K 个 XXX”类型的题都可以按这个流程走先想清楚能不能在一次遍历中直接拿到目标。不能的话第一反应是哈希表统计。再想 K 的规模。K 很小用堆K 接近 N用快速选择数据范围可知且内存够用桶。最后想能否在线处理。如果数据流式到达堆是唯一的常规解。这个套路可以直接迁移到“前 K 个最频繁字符串”“出现次数超过 N/K 的元素”“数组中第 K 大”等一堆题目上。尤其是“数组中第 K 大”其实就是只差一步的简化版不需要统计频次直接对原数组做快速选择。所以很多面试官会把 347 当作一个分水岭能讲清楚它说明你对分治、堆和哈希表的底层理解是连贯的。我在实际刷题时还有一个习惯每道题至少写两版答案。第一版用最容易想通的方法第二版用最优方法然后对比两版代码的边界条件差异。这道题我推荐你至少写堆和快速选择两版因为它们的边界陷阱完全不同写多了之后你对 partition 和堆调整的理解会明显上一个台阶。最后分享一个我自己的实操体会面试写这道题时不要一上来就写代码先在白板上画一个迷你数组比如[1,1,1,2,2,3]把频次统计、堆的逐步变化过程画出来。画完这十几秒你的思路会清晰很多代码也不容易漏边界。这个方法我用过很多次远比埋头硬写稳当。希望这篇拆解也能帮你在下一次遇到“前 K 个高频元素”时不仅写对还能讲明白为什么对。