# 347 - Top K Frequent Elements

解法一 - Min Heap

我們可以把 <num, freq> 放進 min heap 中，裡面存的就是 freq 前 K 大的 num。但一開始還得先算出每個 num 的 freq，所以需要先花 O(n) 的時間建立起 num, freq 的 pair，時間複雜度是 O(n + n*logk)。

實作如下：

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // Get the freq of each num
        unordered_map<int, int> freqMap;
        for(auto& n: nums) {
            freqMap[n]++;
        }

        // Put all <num, freq> pair into min heap
        priority_queue<pair<int, int>, vector<pair<int, int>>, comp> minHeap;
        for(auto& p: freqMap) {
            minHeap.push(p);

            if(minHeap.size() > k) {
                minHeap.pop();
            }
        }

        // Put all num in min heap into result
        vector<int> res;
        for(int i = 0; i < k; ++i) {
            res.push_back(minHeap.top().first);
            minHeap.pop();
        }

        return res;
    }

private:
    struct comp {
        bool operator() (const pair<int, int>& p1, const pair<int, int>& p2) {
            return p1.second > p2.second;
        }  
    };
};