算法-栈和队列：前k个高频元素

在一个数组里找出出现频率前k高的元素。

思路解析：

1. 找出每个元素出现的频率（可以用map）；
2. 按照频率高低来排序（优先级队列）；
3. 找出前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;
}