力扣第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_map
        unordered_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，则弹出堆顶元素，保证堆的大小为k
                minHeap.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，表示左边元素应该排在右边元素之前或者与之相等。

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