🦝 347.前k个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
思路
基本思想
为了找出出现频率前k个的元素，首先肯定是先统计出元素出现的频率，一个元素对应一个频率，所以是成对出现的，所以考虑使用map来存储元素出现的频率
统计完元素出现的频率，需要对频率进行排序，但是正常的map排序都是对键进行排序，而我们统计时，元素出现的频率保存在了值上，所以不能使用map进行排序
此时借助到了优先级队列，优先级队列中默认使用元素的<来排序、但是这里我们使用map存储元素，元素是以pair的形式存在，需要针对pair的second进行排序，所以需要自定义排序规则，一旦需要指定自定义的排序规则，就需要手动指定底层的存储容器
当排序规则制定好之后，需要确保优先级队列中存储的是前k个高频元素，所以需要建立小根堆，不建立大根堆的原因是因为大根堆删除元素时删除的是最大的元素，无法将这些元素保留
当将统计过频率的元素形成的pair都插入优先级队列中，最后剩下来的k个元素就是所要的元素，此时直接将pair中的first元素拿出来就是所求的结果
执行流程
- 统计元素出现的频率
- 对频率排序
- 将剩下的pair中的元素取出来形成vector作为最后的结果
- 返回结果
代码
根据以上分析，得出以下代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| 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; // map<nums[i],对应出现的次数>
for (auto num:nums) {
map[num]++;
}
// 对频率排序
// 定义一个小顶堆，大小为k
//优先级队列的底层存储容器为vector
//要想自定义排序规则，就需要手动指定底层存储容器
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;
// 用固定大小为k的小顶堆，扫面所有频率的数值
for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
pri_que.push(*it);
if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
pri_que.pop();
}
}
// 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组
vector<int> result(k);
for (int i = k - 1; i >= 0; i--) {
result[i] = pri_que.top().first;
pri_que.pop();
}
return result;
}
};
|
总结
主要是对频率的排序，无法使用正常的排序规则，所以借助了优先级队列进行排序
优先级队列使用自定义排序规则时需要手动指定底层存储的容器，因为在创建优先级队列时，需要确保底层容器中的元素能够根据你的自定义排序规则正确地构建堆结构。