用C++ priority_queue 小顶堆搞定LeetCode 347：前K个高频元素（附完整代码）

用C++ priority_queue小顶堆高效解决LeetCode 347：前K个高频元素

在算法面试中，"Top K"问题几乎是必考题。LeetCode 347要求找出数组中出现频率前K高的元素，看似简单，但如何在O(n log k)时间复杂度和O(n)空间复杂度内高效解决？本文将带你深入理解如何利用C++ STL中的priority_queue配合小顶堆这一利器，以最优方式攻克此题。

1. 问题分析与算法选择

题目给定一个非空的整数数组，返回其中出现频率前K高的元素。例如：

输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]

为什么选择小顶堆而非大顶堆？

• 大顶堆方案：将所有元素入堆，然后弹出前K个。时间复杂度O(n log n)，不够高效
• 小顶堆方案：维护一个大小为K的堆，当堆满后，新元素与堆顶比较。时间复杂度优化为O(n log k)

提示：当需要维护"前K个最大"时，小顶堆可以保证堆顶是当前K个中的最小值，便于快速淘汰更小元素。

2. 核心实现步骤拆解

2.1 哈希表统计频率

首先需要统计每个元素的出现频率。C++中unordered_map是最佳选择：

unordered_map<int, int> freqMap; for (int num : nums) { freqMap[num]++; }

2.2 定义小顶堆的比较方式

priority_queue默认是大顶堆，我们需要自定义比较器来实现小顶堆：

auto cmp = [&freqMap](int a, int b) { return freqMap[a] > freqMap[b]; }; priority_queue<int, vector<int>, decltype(cmp)> minHeap(cmp);

2.3 维护大小为K的堆

遍历频率表，保持堆中始终是当前看到的前K高频元素：

for (auto& [num, count] : freqMap) { if (minHeap.size() < k) { minHeap.push(num); } else if (count > freqMap[minHeap.top()]) { minHeap.pop(); minHeap.push(num); } }

3. 完整代码实现

#include <vector> #include <queue> #include <unordered_map> #include <algorithm> using namespace std; vector<int> topKFrequent(vector<int>& nums, int k) { // 统计频率 unordered_map<int, int> freqMap; for (int num : nums) { freqMap[num]++; } // 定义小顶堆比较函数 auto cmp = [&freqMap](int a, int b) { return freqMap[a] > freqMap[b]; }; priority_queue<int, vector<int>, decltype(cmp)> minHeap(cmp); // 维护大小为K的堆 for (auto& [num, count] : freqMap) { if (minHeap.size() < k) { minHeap.push(num); } else if (count > freqMap[minHeap.top()]) { minHeap.pop(); minHeap.push(num); } } // 提取结果 vector<int> result; while (!minHeap.empty()) { result.push_back(minHeap.top()); minHeap.pop(); } reverse(result.begin(), result.end()); return result; }

4. 复杂度分析与优化思考

时间复杂度分析：

空间复杂度：

• 哈希表存储：O(n)
• 堆存储：O(k)

进一步优化方向：

1. 当k接近n时，可以考虑直接排序后取前k个
2. 对于超大n但k很小的情况，本方案已经是最优
3. 可以使用nth_element进行部分排序，但实现复杂度较高

5. 实际面试中的变体与应对

面试官可能会提出以下变体问题，考察对算法的深入理解：

1. 如果数据是流式输入怎么办？

   • 需要设计一个在线算法，持续维护当前的前K高频元素
   • 依然可以使用小顶堆，但需要定期或按批次处理

2. 如何处理频率相同的元素？

   • 当前实现会按照遍历顺序保留，可以修改比较函数加入次要比较条件

3. 如何扩展到分布式环境？

   • 考虑MapReduce框架，mapper统计局部频率，reducer合并后应用堆算法

6. 小顶堆在其他Top K问题中的应用

这种"维护大小为K的堆"的技巧可以推广到多种场景：

• LeetCode 215：数组中的第K个最大元素
• 求前K个最常搜索词
• 推荐系统中的热门物品筛选
• 日志分析中的高频错误统计

每种场景下，只需要调整：

1. 统计阶段的数据结构
2. 堆中存储的内容
3. 比较函数的具体实现

7. 调试技巧与常见陷阱

在实现过程中，容易遇到以下问题：

1. 比较函数定义错误

   • 错误示例：return a > b（比较的是元素本身而非频率）
   • 正确做法：必须通过频率表比较

2. 结果顺序问题

   • 从小顶堆弹出的顺序是频率从低到高
   • 需要反转结果数组

3. 边界条件处理

   • k=0或k>n的情况
   • 所有元素频率相同的情况
   • 输入为空的情况

调试时可以先用小测试案例验证：

vector<int> test = {1,1,2,2,2,3}; auto result = topKFrequent(test, 2); assert(result[0] == 2); assert(result[1] == 1);

8. 性能对比：小顶堆 vs 其他方法

为了直观理解小顶堆的优势，我们对比几种常见解法：

在实际项目中，根据数据特性和k值大小选择最合适的算法。小顶堆方案因其通用性和稳定性，通常是首选。