• 力扣第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 <= 105
    • k 的取值范围是 [1, 数组中不相同的元素的个数]
    • 题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的

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

    思路和解题方法

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

            接着,定义了一个 mycomparison 类,重载了小于号运算符 operator(),用于在priority_queue中实现从小到大排序(即小顶堆)。小顶堆的第二个值即为元素出现次数,按次数从小到大排序,代码如下:

    1. class mycomparison {
    2. public:
    3. bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
    4. return lhs.second > rhs.second; // 小于号的比较操作,根据second(即频率)从小到大排序
    5. }
    6. };

            接着,在函数内部定义了一个小顶堆 priority_queue,用于存储出现次数最多的前 k 个元素。使用 for 循环遍历 map 中所有的键值对,将当前元素的键值对插入小顶堆中,并保证小顶堆的大小不超过 k。当小顶堆的大小超过 k 时,弹出堆顶,保证堆的大小恰好为 k。

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

    复杂度

            时间复杂度:

                    O(nlogk)

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

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

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

    3. 取出前 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++ 代码

     ​
    
    1. class Solution {
    2. public:
    3. vector<int> topKFrequent(vector<int>& nums, int k) {
    4. // 统计元素出现频率,使用哈希表unordered_map
    5. unordered_map<int, int> countMap;
    6. for (int num : nums) {
    7. countMap[num]++;
    8. }
    9. // 创建小顶堆,并维护大小为k,使用优先队列priority_queue
    10. // 小顶堆中存储pair>,第一个元素表示元素出现的频率,第二个元素表示对应的元素值
    11. priority_queueint, int>, vectorint, int>>, greaterint, int>>> minHeap;
    12. for (auto& p : countMap) {
    13. // 将当前键值对(p.first为元素值,p.second为元素出现的频率)插入到小顶堆中
    14. // 注意:插入时要将pair的第一个元素赋值为出现频率,第二个元素赋值为元素值
    15. minHeap.emplace(p.second, p.first);
    16. if (minHeap.size() > k) {
    17. // 如果小顶堆的大小超过了k,则弹出堆顶元素,保证堆的大小为k
    18. minHeap.pop();
    19. }
    20. }
    21. // 输出前k个高频元素,从小顶堆中取出元素
    22. vector<int> result(k);
    23. for (int i = k - 1; i >= 0; --i) {
    24. result[i] = minHeap.top().second; // 取出小顶堆中堆顶元素(即出现频率最小的元素),并将其值存储到结果数组中
    25. minHeap.pop(); // 弹出堆顶元素
    26. }
    27. return result;
    28. }
    29. };

    1. class Solution {
    2. public:
    3. // 定义一个小于号比较类,用于小顶堆的排序
    4. class mycomparison {
    5. public:
    6. bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
    7. return lhs.second > rhs.second; // 按出现次数从少到多排序
    8. }
    9. };
    10. vector<int> topKFrequent(vector<int>& nums, int k) {
    11. unordered_map<int, int> map; // 定义哈希表来统计元素出现频率
    12. for (int num : nums) { // 遍历数组
    13. map[num]++; // 更新哈希表中对应元素的出现次数
    14. }
    15. priority_queueint, int>, vectorint, int>>, mycomparison> pq; // 定义一个小顶堆
    16. for (auto& p : map) { // 遍历哈希表中的键值对
    17. pq.push(p); // 将键值对插入到小顶堆中
    18. if (pq.size() > k) { // 如果小顶堆的大小超过k,则弹出堆顶元素
    19. pq.pop(); // 弹出的是出现次数最少的元素
    20. }
    21. }
    22. vector<int> res(k); // 定义结果数组
    23. for (int i = k - 1; i >= 0; i--) { // 从小顶堆的堆顶开始依次取出前K个高频元素
    24. res[i] = pq.top().first; // 取出元素(堆顶),存储到结果数组中
    25. pq.pop(); // 弹出堆顶元素,即出现次数最少的元素
    26. }
    27. return res;
    28. }
    29. };

    相关知识

    1.优先队列priority_queue

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

    priority_queueint, int>, vectorint, int>>, greaterint, int>>> minHeap;

    其中:

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

    • vector> 表示底层容器使用vector存储元素。

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

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

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

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

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

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

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

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

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

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

  • 相关阅读:
    Word控件Spire.Doc 【表单域】教程(五):如何在 C# 中更新 Ask 字段
    深入理解JVM虚拟机第八篇:引导类加载器 、拓展类加载器、应用类加载器与自定义类加载器
    【软考学习3】数据表示——浮点数计算 + 单精度浮点数IEEE754计算
    【技术美术知识储备】图形渲染管线1.0-基本概念&CPU负责的应用阶段
    Node.js精进(8)——错误处理
    2、TCP协议基础
    python中的NaN在质量控制中怎么处理?
    高能预警!第十七届 D2 第一波话题新鲜出炉 ~
    Android 匿名共享内存的使用
    基于 SpringBoot+Vue 的口腔管理平台,附源码,数据库
  • 原文地址:https://blog.csdn.net/jgk666666/article/details/133531294