【LeetCode347】前K個高頻元素（pair）

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