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;
    }
}; 

  

 

  
1
  
2
  
3
  
4
  
5
 

（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;
    }
};

  

 

  
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
 

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个高频元素存入vector
            res.push_back(q.top().second);
            q.pop();
        }
        return vector<int>(res.rbegin(), res.rend());
    }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
 

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

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/113817077