当前位置: 首页> 健康> 养生 > b站在哪付费推广_品牌推广图片_小程序开发制作_国家卫生健康委

b站在哪付费推广_品牌推广图片_小程序开发制作_国家卫生健康委

时间:2025/7/11 15:25:09来源:https://blog.csdn.net/qq_51956059/article/details/147278770 浏览次数:0次
b站在哪付费推广_品牌推广图片_小程序开发制作_国家卫生健康委

这段代码实现的是:在一个整数数组中,找出出现频率最高的前 k 个元素。也就是说,你想找的是出现次数最多的 k 个数字。

class Solution {
public:vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int, int> mp;priority_queue<pair<int, int>> pq;vector<int> res;for(int num : nums) {mp[num]++;}for(auto it = mp.begin(); it != mp.end(); it++) {pq.push(pair<int, int>(it->second, it->first));}while(k--) {res.push_back(pq.top().second);pq.pop();}return res;}
};


✅ 一、题目简述

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

输出:[1, 2]

因为 1 出现了 3 次,2 出现了 2 次,是前两个出现次数最多的。


✅ 二、算法思路详解

你采用了哈希表 + 大顶堆的做法,时间复杂度是 O(n log n),思路清晰、非常经典。

1. 使用 unordered_map 统计频率:

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

这一步把所有数字出现的频率都存入哈希表 mp,键是数字,值是出现次数。

以 nums = [1,1,1,2,2,3] 为例,map 最终为:

{1: 3,2: 2,3: 1
}


2. 使用 priority_queue 构建最大堆(默认大顶堆):

priority_queue<pair<int, int>> pq;
for (auto it = mp.begin(); it != mp.end(); ++it) {pq.push({it->second, it->first});
}

将频率(it->second)作为堆的优先级,pair 的第一个元素作为排序依据。

这样堆顶就是当前频率最大的数字


3. 取出前 k 个频率最高的元素:

while (k--) {res.push_back(pq.top().second);pq.pop();
}

• 每次从堆顶取出元素,把数字加入结果数组 res

• 取出 k 次,就得到了频率最高的前 k 个元素


✅ 三、时间复杂度分析

步骤

时间复杂度

哈希统计频率

O(n)

构建最大堆(n 个元素)

O(n log n)

取出前 k 个元素

O(k log n)

总复杂度

O(n log n),空间 O(n)


✅ 四、举个例子运行一下

输入:

nums = [4, 1, 1, 2, 2, 3, 3, 3]
k = 2

第一步统计频率:

mp = {1: 2,2: 2,3: 3,4: 1
}

第二步建堆:

堆内容为(按 pair<int, int> 构建,自动按频率排序):

(3, 3)
(2, 2)
(2, 1)
(1, 4)

第三步取前 2 个:

• 第一次弹出 (3, 3) → 加入结果:3

• 第二次弹出 (2, 2) 或 (2, 1) → 加入结果:2(或 1)

返回结果可能是 [3, 2] 或 [3, 1],顺序不重要


✅ 总结

步骤

技术细节

频率统计

使用哈希表

快速找最大频率值

使用大顶堆

保证前 k 高频

每次取堆顶 k 次


详细讲一下这句 C++ 容器的用法:

priority_queue<pair<int, int>> pq;

这是在声明一个 大顶堆(最大优先队列),元素类型是 pair<int, int>,即两个整数的组合。


✅ 一、什么是 priority_queue?

priority_queue 是 C++ STL 中的一个容器适配器,默认是一个大顶堆。也就是说,堆顶(top())总是最大的那个元素。


✅ 二、pair 的排序规则(默认)

当你放入的是 pair<int, int> 类型时,它默认使用 字典序排序,也就是比较:

• 先比第一个元素(first),大的优先

• 如果第一个相等,再比第二个元素(second)

🌰 例子:

priority_queue<pair<int, int>> pq;
pq.push({3, 100});
pq.push({2, 200});
pq.push({3, 50});

堆的排序顺序是:

• {3, 100}(最大,排在堆顶)

• {3, 50}

• {2, 200}(最小)


✅ 三、使用方法总结

1. 声明

priority_queue<pair<int, int>> pq;

2. 插入元素

pq.push({次数, 元素值});

3. 取堆顶

pq.top(); // 返回 pair,最多的那个(按 pair 排序规则)

4. 删除堆顶

pq.pop();

5. 判断是否为空

pq.empty();


✅ 四、应用场景(比如频率统计)

在你前面这题:

// 频率作为 first,元素值作为 second
pq.push({it->second, it->first});

也就是 pq 中每个元素是 {频率, 数字},这样:

• top() 总是出现次数最多的数字

• 弹出 k 次,就得到了 top-k frequent elements


✅ 五、自定义排序(扩展)

如果你想改成小顶堆(比如为了保留最小的前 K 个),可以这么写:

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

这里使用了第三个模板参数 greater<>,改成最小堆。


🧠 总结小抄

声明方式

类型

默认顺序

priority_queue<int>

整数堆

最大值优先

priority_queue<pair<int,int>>

pair堆

按 first 降序,再按 second 降序

priority_queue<..., greater<>>

任意类型

最小值优先

关键字:b站在哪付费推广_品牌推广图片_小程序开发制作_国家卫生健康委

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: