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

题目

347. 前 K 个高频元素

中等

相关标签

数组 哈希表 分治 桶排序 计数 快速选择 排序 堆（优先队列）

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

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

示例 2:

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

提示：

1 <= nums.length <= 105k 的取值范围是 [1, 数组中不相同的元素的个数]题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

思路和解题方法

        首先，在函数内部定义了一个 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，表示左边元素应该排在右边元素之前或者与之相等。

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

觉得有用的话可以点点赞，支持一下。

如果愿意的话关注一下。会对你有更多的帮助。

每天都会不定时更新哦  >人<  。