347. Top K Frequent Elements

解題思路

這題可以用 maxHeap 的概念來解。又因為 sort 的依據是出現次數，但 key 是數字本身的值，所以用 pair。

首先建立 integer 跟其出現次數的 map，接著再從該 map 轉換放進 maxHeap 中。由於 priority_queue 是看 first 來 sort ，因此這邊選擇以 {e.second, e.first} 的形式來 push。

接下來只要 pop k 次 maxHeap 即可。注意此時要的是 maxHeap 的 second。

程式碼

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        priority_queue<pair<int, int>> maxHeap; // integer, occurence
        vector<int> ans;
        unordered_map<int, int> mp;
        for(int i=0; i<nums.size(); i++)
            mp[nums[i]]++;
        
        for(auto e:mp)
            maxHeap.push({e.second, e.first});
        
        for(int i=0; i<k; i++)
        {
            ans.push_back(maxHeap.top().second);
            maxHeap.pop();
        }
        return ans;
    }
};