1.题目

2.思路

（1）方法和【LeetCode215】数组中的第k个最大元素（小顶堆—priority_queue）相同（利用小顶堆，不断加入且保持优先队列恰好为k个元素）。不过注意是将每个元素出现次数加入小顶堆中——所以一开始用unordered_map统计每个元素的出现次数，而因为哈希表的key（即元素）也需要保存，所以优先队列priority_queue里的元素不是int型了：可以用pair<int,int>。

（2）在优先队列的排序参数需要重写（因为若直接用greater则是先对pair的first排序，再对second排序），而现在我们只要对second排序，所以符号重载：

struct cmp{bool operator()(pair<int,int>&a,pair<int,int>&b){return a.second>b.second;}
}; 

（3）小顶堆的堆顶是最小的，所以为了根据频数找出前K大高频元素（从大到小），要依次将堆顶元素从末尾开始赋值给ans数组。

3.代码

class Solution {
struct cmp{bool operator()(pair<int,int>&a,pair<int,int>&b){return a.second>b.second;}
}; 
public: vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int,int>mp(nums.size());//key为i时出现的次数for(int i=0;i<nums.size();i++){mp[nums[i]]++;}priority_queue<pair<int,int>,vector<pair<int,int>>,cmp>minheap;for(auto it=mp.begin();it!=mp.end();it++){minheap.push(make_pair(it->first,it->second));if(minheap.size()==k+1){minheap.pop();//保持k个}}vector<int>ans(k);for(int i=k-1;i>=0;i--){ans[i]=minheap.top().first;minheap.pop();}return ans;}
};

4.不使用符号重载的版本

如果不使用符号重载，

class Solution {
public:vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int,int> map;for(int i : nums) map[i] ++; //遍历priority_queue< pair<int,int>, vector< pair<int,int> >, greater< pair<int,int> > > q; //最小堆for(auto it : map) if(q.size() == k) { //队列满了if(it.second > q.top().first) { //堆排q.pop();q.push(make_pair(it.second, it.first));}}else q.push(make_pair(it.second, it.first));vector<int> res;while(q.size()) { //将优先队列中k个高频元素存入vectorres.push_back(q.top().second);q.pop();}return vector<int>(res.rbegin(), res.rend());}
};

（1）sort对vector中pair排序+优先队列的排序
（2）priority_queue的用法（含自定义排序方式）