算法-栈和队列:前k个高频元素
在一个数组里找出出现频率前k高的元素。
思路解析:
- 找出每个元素出现的频率(可以用map);
- 按照频率高低来排序(优先级队列);
- 找出前k个元素。
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
class MyComparison{ //单调队列,队头队尾从大到小
public:
//定义小顶堆 >
bool operator()(const pair<int, int>&lhs,const pair<int, int>&rhs){
return lhs.second > rhs.second;// 注意不要忘记second!!!因为是map所以才重写,如果只有int那么使用greater<int>即可定义小顶堆
}
};
vector<int> topKeys(vector<int> nums,int k){
// 1. 找出每个元素出现的频率(可以用map);
unordered_map<int,int> umap;
for(int i = 0; i < nums.size(); i++){
umap[nums[i]]++;
}
// 2. 按照频率高低来排序(优先级队列);
priority_queue<pair<int, int>,vector<pair<int, int>>,MyComparison> priQue;//定义一个优先队列,采用小顶堆
for(unordered_map<int, int>::iterator it = umap.begin();
it!= umap.end(); it++){//将map内所有元素都推入优先队列中,如果队列的元素超过k个,那么就弹出队头(队头永远是最小的)
priQue.push(*it);
if(priQue.size()>k){
priQue.pop();
}
}
// 3. 找出前k个元素。
vector<int> res(k);
for(int i = k-1; i >= 0; i--){ //小顶堆先弹出的是最小的元素,所以倒序存入res
res[i] = priQue.top().first;
priQue.pop();
}
return res;
}
int main(){
vector<int> nums = {2,4,4,-2,-4,3,1,5,5,5,7,8,9,6,8};
int k;
while (cin>>k) {
vector<int> res = topKeys(nums,k);
for(int i = 0; i < res.size(); i++){
cout<<res[i]<<" ";
}
cout<<endl;
}
return 0;
}