前k个高频元素全解：哈希表、堆与桶排序的实战对比

准备用一篇实战向的博文来拆解“前k个高频元素”这道题。这道题我在刷题打卡系列里做到第20篇时，真正理解了为什么它被反复拿来面试——因为它一个题目串起了哈希表、堆、桶排序、快速选择四个经典知识点，而且每一个解法在C++里实现时都有值得展开的细节。下面是我自己的完整复盘。

1. 题目到底在考什么：从直觉到复杂度分析

LeetCode 347这道题，题面非常简单：给你一个整数数组 nums 和一个整数 k，请你返回其中出现频率前 k 高的元素。示例就是nums = [1,1,1,2,2,3], k = 2，输出[1,2]。

但简单题面背后藏着的东西一点都不简单。我在打卡系列里做过不少哈希表题目，通常套路就是遍历一遍统计频次，然后按频次排序取前k个。这道题也一样，核心就两个步骤：统计频次和取前k个。然而恰恰是第二步，把题目从“会做”拉升到了“懂做”的层次。

先说个很反直觉的点：大多数人第一反应是用大根堆，也就是把所有元素按频率丢进一个最大堆，然后弹出k次。这个思路没有错，但如果你真的把它写成AC代码，会发现一个问题——空间复杂度是O(n)。当数组有100万个不同元素时，堆里也要放100万个节点，这显然不够优雅。

这道题真正考察的是你对“top k”问题的理解深度。在面试场景里，面试官想要的不是你能AC，而是你能不能说出为什么小根堆比大根堆好，能不能在数据规模巨大时给出线性时间的解法。所以这篇文章我会从最暴力的解法开始，一步步演进到最优解，同时把C++实现里那些容易写错、容易踩坑的细节全部摊开讲。

我觉得它值得被放进打卡系列里作为第20篇，还有一个原因：它是少数几道能同时复习哈希表、堆、桶排序、快速选择四个知识点的题。如果你刷题有一定量级，会发现这些知识在后面的题目里会被反复用到。把这一题吃透，等于把四条知识线在脑子里打通了一次。

2. 三种主流解法的思路演进：大根堆、小根堆、桶排序

2.1 大根堆：最容易想到但暗藏问题

我先说大多数人会写的大根堆方案。思路非常直白：先用unordered_map统计每个数字出现的次数，然后把这些{数字, 次数}对全部放进一个大根堆，堆顶永远是当前频率最大的元素，弹出k次就得到答案。

用C++写出来大概长这样：

vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int, int> freq; for (int num : nums) freq[num]++; priority_queue<pair<int, int>> pq; // 默认按 first 降序，first 放频率 for (auto& p : freq) { pq.push({p.second, p.first}); // 注意顺序：频率放前面 } vector<int> res; for (int i = 0; i < k; i++) { res.push_back(pq.top().second); pq.pop(); } return res; }

这段代码能AC，但确实存在刚才说的空间问题。还有一个细节容易写反：pair的排序是先比first再比second，所以你一定要把频率放到first位置。如果写成了pq.push({p.first, p.second})，那排序就按数字大小来，结果全错。

我最早写这道题时就栽在这个顺序上，调试了半天才发现堆顶元素根本不是频率最大的那个。这种错误编译器不会报错，逻辑上也很难一眼看出来，只能说pair的默认排序规则太容易让人想当然了。

再说一句，大根堆方案的时间复杂度是O(n log n)，因为每个元素入堆都要log n的调整时间。空间O(n)。作为“能AC”的版本没问题，但如果你在优化阶段还抱着这个方案不放，面试官大概率会追问一句“能不能降低空间复杂度”。

2.2 小根堆：空间复杂度从O(n)降到O(k)

小根堆的思路和上面刚好相反：维护一个大小为k的小根堆，堆顶是堆里频率最小的那一个。遍历哈希表时，如果堆没满就直接入堆；如果堆满了，只有当当前元素的频率大于堆顶频率时才替换。这样遍历结束后，堆里留下的正好是频率最大的k个元素。

vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int, int> freq; for (int num : nums) freq[num]++; auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) { return a.second > b.second; // 小根堆：频率小的在堆顶 }; priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp); for (auto& p : freq) { if (pq.size() < k) { pq.push(p); } else if (p.second > pq.top().second) { pq.pop(); pq.push(p); } } vector<int> res; while (!pq.empty()) { res.push_back(pq.top().first); pq.pop(); } return res; }

这个版本的精髓在于：堆里永远只有k个元素，空间复杂度O(k)。当k远小于n时（比如k=10，n=100万），这个优势非常可观。时间复杂度是O(n log k)，因为每个元素的入堆操作最多log k级别。

不过这里有几个容易踩的坑：

• priority_queue默认是大根堆，想要小根堆必须自定义比较器。
• 自定义比较器的语义是“谁优先级更低”，也就是true表示a应该排在b后面（更靠近堆底），所以a.second > b.second才能让频率小的元素待在堆顶。这个逻辑第一次接触会绕，我建议自己推一遍：默认情况下less让大的在堆顶，改成greater就让小的在堆顶。
• 比较器可以是函数指针、函数对象、lambda。用lambda最简洁，但因为lambda类型是匿名的，声明队列时要用decltype(cmp)来拿类型，同时构造函数里要传入cmp实例。

2.3 桶排序：把O(n log n)干到O(n)

如果你对时间复杂度有执念，那可以上桶排序（计数排序思想）。思路是：元素最多出现nums.size()次，那我们就开一个freq + 1大小的数组，用频率当下标，把相同频率的元素放进同一个桶里。最后从桶数组末尾往前遍历，取够k个元素。

vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int, int> freq; for (int num : nums) freq[num]++; int n = nums.size(); vector<vector<int>> buckets(n + 1); for (auto& p : freq) { buckets[p.second].push_back(p.first); } vector<int> res; for (int i = n; i >= 1 && res.size() < k; i--) { for (int num : buckets[i]) { res.push_back(num); if (res.size() == k) break; } } return res; }

这个解法的时间复杂度严格O(n)，空间复杂度O(n)。它没有任何对数项，因为桶的存取都是O(1)。我第一次写出这个版本时有一种“原来这题可以做到线性”的震撼感。桶的数量等于最大频率，在数组长度很大但频率分布集中时表现尤其好。

缺点也明显：空间开销大，要开一个n+1大小的二维vector。如果数组里有100万个元素，就算每个数只出现一次，这个桶数组也要吃100万量级的空间。但对力扣这道题的数据规模来说完全没问题。

2.4 复杂度对比与面试选择策略

我把三种方案的核心参数整理成下面这张表，方便直观对比：

如果在面试中遇到这题，我的建议是：先讲小根堆方案，因为它兼顾了空间和时间，是工程上最常用、也最能展现你懂“top k”本质的方案。面试官如果继续追问“能不能O(n)”，再掏出桶排序。千万不要一上来就甩桶排序——不是不可以，但你会少一个展示思维演进过程的机会。

还有一点值得提：其实还有第四种方案，快速选择（Quick Select），平均O(n)最坏O(n²)。我在打卡记录里把它作为延伸学习，因为实现复杂度比桶排序高不少，但它是“无序数组中找第k大”这一大类问题的通用解法。第215题“数组中的第K个最大元素”就是它的典型应用场景。等把347彻底吃透，我建议你顺手把215也刷掉，两道题对照着看会很启发。

3. C++实现细节：STL容器、比较器与其他隐蔽坑

前面代码能AC，但如果你想写出更地道的C++，有几个细节值得单独拎出来说。这些细节平时写业务代码可能用不上，但刷题时几乎每题都会遇到。

3.1 unordered_map 与 map：这道题的选择没有悬念

统计频次时，用unordered_map<int, int>就好。它的底层是哈希表，查找和插入平均O(1)。如果你用基于红黑树的map，每次操作是O(log n)，全局下来会慢一截。虽然力扣的数据量不一定能感受到差距，但刷题的习惯要在平时养成。

这里有个容易纠结的点：遍历unordered_map时，元素顺序是无序的。但你不需要有序，因为后续要么进堆要么进桶，都不依赖遍历顺序。在很多场景下“不用有序”就意味着“用unordered_map”，可以把这个当作一个条件反射。

3.2 priority_queue 的比较器：为什么lambda能写但要注意捕获

自定义比较器有这样几种写法：函数指针、仿函数（函数对象）、lambda表达式。lambda最推荐，因为它可以就近定义、逻辑清晰。但有个隐蔽的坑：lambda表达式的类型是独一无二的匿名类型，所以声明priority_queue时必须用decltype(cmp)来推导类型，同时构造时传cmp进去。

auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) { return a.second > b.second; }; priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);

如果你图省事把比较器写成局部函数再用函数指针，会有两个问题：一是函数指针作为模板参数时，需要类型一致；二是函数指针通常没有inline优化，性能略差。日常刷题用lambda就够了。

还要注意，priority_queue的比较器与sort的比较器语义相反。sort中a < b表示升序，而priority_queue中a < b（默认less）表示大根堆。如果你在小根堆里写成a.second < b.second，你会发现堆顶是频率最大的——跟你设想的完全相反。我在这上面吃过亏，建议你以后写堆相关代码时，先写一行注释：// 小根堆：频率小的在堆顶。

3.3 vector 加 sort 的“偷懒”写法

如果你追求代码量最少，第三种方案也很香：把{频率, 数字}的pair放进vector，按频率降序排序，然后取前k个。

vector<pair<int, int>> v; for (auto& p : freq) v.push_back({p.second, p.first}); sort(v.begin(), v.end(), greater<pair<int, int>>()); vector<int> res; for (int i = 0; i < k; i++) res.push_back(v[i].second);

greater是STL自带的谓词，直接让pair按first降序排列，代码非常短。但它的时间复杂度是O(n log n)，空间O(n)，数据量大时能明显感觉到比堆慢。所以我更愿意把它当作一种“确认思路”的验证写法，而不是最终的优雅解法。

3.4 迭代器失效与访问越界：新手最容易忽略的隐蔽问题

桶排序版本里，我用了vector<vector<int>> buckets(n + 1)，访问buckets[p.second]。这里p.second的范围是1到n，下标不会越界。但如果你把桶开成n而不是n + 1，当数组中所有元素都一样、频率刚好等于n时，就会越界访问。力扣的数组下标是从0开始的，但频率的最小值是1（元素出现一次），所以下标1到n都是有效区间，开n + 1是最稳妥的。

另外，在遍历哈希表的过程中，如果你用unordered_map的迭代器做插入操作，可能失效。但这里我们是先统计完再遍历，遍历过程中不修改map，所以没有这个问题。这里没风险，但类似的题里经常有人犯错，提一句帮你建立敏感度。

4. 实测中的意外：我差点因为“排序方向”栽了个跟头

写这题的当天，我之前做过的题目都是靠sort一把梭，所以在这道题上也惯性用了“全部排序取前k”的思路。结果提交之后通过用例倒是不意外，但我越想越觉得不对劲：如果数据不均衡，比如有一个数字出现了50万次，其他数字各出现1次，那sort的时间浪费得很冤。

后来我特意在自己的测试环境里跑了一组大数据：100万个元素，k=5，分别用大根堆、小根堆、桶排序跑，统计耗时。测试方式很简单，用chrono库计时。

#include <chrono> auto start = chrono::high_resolution_clock::now(); // 调用你的函数 auto end = chrono::high_resolution_clock::now(); cout << chrono::duration_cast<chrono::microseconds>(end - start).count() << "us" << endl;

结果并没有出乎意料：桶排序最快，小根堆次之，大根堆最慢。但有趣的是小根堆与大根堆的差距没有想象中大，原因在于unordered_map的遍历本身就占了很大一部分时间，堆操作的差异被稀释了。这说明一个问题：刷题时也不要只看复杂度，实际运行才是硬道理。

这个测试还让我意识到另一件事：不要盲信任何“最优解”的结论，要用数据说话。桶排序虽然理论上是O(n)，但它有额外的vector 内存分配开销，在某些场景下未必比小根堆快。

5. 从“能AC”到“懂原理”：C++项目里的延伸思考

5.1 和“数组第K大元素”的家族关系

做完了前k个高频元素，我在打卡系列里紧接着刷了第215题数组中的第K个最大元素。两道题是同一个套路的不同变种：都是“在无序集合里找前k个最大元素”，只不过215题的数据源是数组本身，而347题的数据源是频率统计结果。解法上都绕不开快速选择或堆。

如果你有时间，我建议把以下这些题目串起来刷：

• LeetCode 215：数组中第K个最大元素
• LeetCode 347：前k个高频元素（本篇）
• LeetCode 692：前K个高频单词
• LeetCode 973：最接近原点的K个点
• LeetCode 1834：单线程CPU

这几道题看起来五花八门，但核心全部是“如何在一堆东西里高效取出top k”。一旦你建立了“top k问题 = 堆/快速选择”的思维模式，遇到新题就能很快定位解法框架。

5.2 在真实项目中的低频但关键应用

有人觉得这种题在实际项目里“用不到”，这是一种误解。虽然你不会天天手写快速选择，但“从海量数据中提取TopN”的需求在日志分析、榜单推荐、热词统计里太常见了。比如线上服务每天产生千万条访问日志，要统计访问量最高的100个接口，你不可能把所有数据读进内存然后sort——这时候小根堆的思路直接用得上，业务代码里你甚至可以借助std::priority_queue一行行处理流式数据，内存占用永远只有k。

我之前在维护一个推荐系统时，就遇到过类似需求：从百万级物品中筛出每个用户最感兴趣的10个物品。用大根堆就是暴力取前10，但100万用户就会导致内存暴涨；换成小根堆，每个用户只需要维护大小为10的堆，性能提升一个数量级。这篇文章里写的小根堆代码，几乎可以直接搬到那种业务场景。

5.3 延伸：从静态数据到数据流的Top K

347题是静态数据，但如果数据是源源不断到来的呢？这就是数据流TopK问题。方法也很直接：维护一个大小为k的小根堆，每来一个新元素就和堆顶比，比堆顶大就入堆并弹出堆顶。复杂度O(n log k)，空间O(k)。这其实就是347题小根堆方案在流式场景下的自然延伸。

我后来拿这个思路处理过一个日志监控需求：线上服务每秒产生大量错误日志，我们需要实时维护“最近5分钟出现次数最多的前20个错误类型”。方案就是一个带时间窗口的哈希表加一个小根堆，窗口过期数据定期清理，性能非常稳。从这个角度说，把这道题吃透不只是为了面试，它真的能帮你解决工程里很实在的问题。

6. 这份打卡记录里我学到的三条经验

最后聊聊这题给我个人的学习收获，也算是我坚持打卡到第20篇的一个小结。

第一，先想清楚所有解法再动手写代码。最初我只想到大根堆，写了一版能AC就以为结束了。后来被提醒空间复杂度可以优化，才一步步走到小根堆、桶排序。如果一开始就花十分钟把所有思路列出来，后面会少走很多弯路。现在我做题的习惯是：先写注释把思路、复杂度、边界情况梳理清楚，再动手。

第二，C++语法细节的坑，一定要亲手踩一遍才记得住。比较器方向搞反、pair顺序写错、忘记加n + 1导致下标越界，这些问题光看别人的代码是看不出来的，只有自己调试时盯着堆顶数据发愣，下一次才能形成条件反射。所以我不建议直接用我的代码AC就完事——把自己想到的每个版本都写一遍，哪怕写得慢。

第三，打卡记录不要只记解法，要记“为什么”。我每道题都会在本地笔记里写一段“这道题卡住我5小时的是哪一步”，过两周回看，比记一堆AC代码有用得多。时间一长，就会发现高频的错误模式其实就那么几种，比如“遍历中修改容器”“排序方向反了”“边界下标忘了处理”。347这道题，只是正好把其中两个坑凑到了同一个页面里。如果你也在跟着打卡刷题，我真心建议你也建一个类似的“踩坑日志”，不要只是收藏题解。