力扣第347题堆（优先队列）经典题 c++ 简易注释版附（相关知识点解答）

题目

347. 前 K 个高频元素

中等

思路和解题方法

首先，在函数内部定义了一个 unordered_map，用于存储每个元素出现的次数。然后使用 for 循环遍历整个数组，将每个元素出现的次数存储到 map 中。

接着，定义了一个 mycomparison 类，重载了小于号运算符 operator()，用于在priority_queue中实现从小到大排序（即小顶堆）。小顶堆的第二个值即为元素出现次数，按次数从小到大排序，代码如下：
class mycomparison {
public:bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) { return lhs.second > rhs.second; // 小于号的比较操作，根据second（即频率）从小到大排序}
};
接着，在函数内部定义了一个小顶堆 priority_queue，用于存储出现次数最多的前 k 个元素。使用 for 循环遍历 map 中所有的键值对，将当前元素的键值对插入小顶堆中，并保证小顶堆的大小不超过 k。当小顶堆的大小超过 k 时，弹出堆顶，保证堆的大小恰好为 k。

最后，再从小顶堆中取出前 k 个元素，按照他们在数组中出现的次数从大到小输出到结果向量中，即可得到出现次数最多的前 k 个元素。

复杂度

时间复杂度:

O(nlogk)

时间复杂度为 O(nlogk)，其中 n 是数组的长度，k 是要求的前 k 个元素的个数。具体分析如下：

遍历整个数组并统计每个元素出现的次数，需要 O(n) 的时间复杂度。

创建小顶堆，并将键值对插入堆中。插入每个元素的时间复杂度为 O(logk)，因为堆的大小最大为 k，所以插入 k 个元素的时间复杂度为 O(klogk)。

取出前 k 个元素，并倒序输出到结果向量中，需要 O(k) 的时间复杂度。

时间复杂度为 O(nlogk + klogk)。当 k 相对于 n 较小时，可以简化为 O(nlogk)。

空间复杂度

O(n+k)

使用了一个 unordered_map 存储每个元素出现的次数，需要 O(n) 的额外空间。同时，使用了小顶堆来存储前 k 个元素，其大小为 k，所以额外空间复杂度为 O(k)。总的空间复杂度为 O(n+k)。

c++ 代码

class Solution {
public:vector<int> topKFrequent(vector<int>& nums, int k) {// 统计元素出现频率，使用哈希表unordered_mapunordered_map<int, int> countMap;for (int num : nums) {countMap[num]++;}// 创建小顶堆，并维护大小为k，使用优先队列priority_queue// 小顶堆中存储pair<pair<int, int>>，第一个元素表示元素出现的频率，第二个元素表示对应的元素值priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;for (auto& p : countMap) {// 将当前键值对（p.first为元素值，p.second为元素出现的频率）插入到小顶堆中// 注意：插入时要将pair的第一个元素赋值为出现频率，第二个元素赋值为元素值minHeap.emplace(p.second, p.first);if (minHeap.size() > k) {// 如果小顶堆的大小超过了k，则弹出堆顶元素，保证堆的大小为kminHeap.pop();}}// 输出前k个高频元素，从小顶堆中取出元素vector<int> result(k);for (int i = k - 1; i >= 0; --i) {result[i] = minHeap.top().second; // 取出小顶堆中堆顶元素（即出现频率最小的元素），并将其值存储到结果数组中minHeap.pop(); // 弹出堆顶元素}return result;}
};

class Solution {
public:// 定义一个小于号比较类，用于小顶堆的排序class mycomparison {public:bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second; // 按出现次数从少到多排序}};vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int, int> map; // 定义哈希表来统计元素出现频率for (int num : nums) { // 遍历数组map[num]++; // 更新哈希表中对应元素的出现次数}priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pq; // 定义一个小顶堆for (auto& p : map) { // 遍历哈希表中的键值对pq.push(p); // 将键值对插入到小顶堆中if (pq.size() > k) { // 如果小顶堆的大小超过k，则弹出堆顶元素pq.pop(); // 弹出的是出现次数最少的元素}}vector<int> res(k); // 定义结果数组for (int i = k - 1; i >= 0; i--) { // 从小顶堆的堆顶开始依次取出前K个高频元素res[i] = pq.top().first; // 取出元素（堆顶），存储到结果数组中pq.pop(); // 弹出堆顶元素，即出现次数最少的元素}return res;}
};

相关知识

1.优先队列priority_queue

代码定义了一个优先队列priority_queue，用于存储出现频率最高的k个元素。具体来说，它的模板参数如下所示：

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;

其中：

pair<int, int> 表示队列中的元素类型为pair，第一个元素是int类型的出现频率，第二个元素是int类型的元素值。

vector<pair<int, int>> 表示底层容器使用vector存储元素。

greater<pair<int, int>> 表示采用greater作为比较函数，即小顶堆，按照出现频率从小到大进行排序。

因此，我们可以通过将键值对（出现次数，元素值）插入到优先队列中，并保证队列大小不超过k。

2.小于号比较操作符重载函数

  bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second; // 按出现次数从少到多排序}};

定义了一个小于号比较操作符重载函数。该函数接受两个pair<int, int>类型的参数lhs和rhs，分别表示堆中的两个元素。在函数内部，它比较了这两个元素的第二个成员（即出现次数），并根据比较结果返回一个布尔值。

如果lhs.second（左边元素的出现次数）大于rhs.second（右边元素的出现次数），则返回true，表示左边元素应该排在右边元素之后；
如果lhs.second小于等于rhs.second，则返回false，表示左边元素应该排在右边元素之前或者与之相等。

由于我们希望堆中的元素按照出现次数从少到多的顺序排列，因此在比较函数中使用了 > 运算符，使得堆中的元素按照从小到大的顺序进行排序。