347. Top K Frequent Elements ------M ~~~~学习写Queue with comparator

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

Note:

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

A:

就是利用了 priority_queue

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> M; // value to count mapping
        for(auto v:nums)
            M[v]++;
        
        auto comparator =  [](const P & p1, const P & p2 ){return p1.count < p2.count;};
        priority_queue<P, vector<P>, decltype(comparator)> q(comparator);
        for(auto & it : M)
        {
            q.push(P(it.first, it.second));
        }
        vector<int> res;
        for(int i =0;i<k;++i)
        {
            auto tmp = q.top();
            res.push_back(tmp.val);            
            q.pop();
        }
        return res;
    }
private:    
    struct P{
        int val;
        int count;
        P(int v,int c):val(v),count(c){}
    };
};

上面的最坏情况还是 O(n * lg(n)). 

因此我们需要限制Queue的size。因此我们选用了maxHeap (这样就不需要自己写comparator）

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> um;
        for(const auto v:nums)
            ++um[v];
        priority_queue<vector<int>, vector<vector<int>>> maxHeap; //max of count as the comparing key
        for(const auto & pair : um){
            int v= pair.first, count = pair.second;
            maxHeap.push({count,v}); // compare count first
        }
        vector<int> res;
        for(int i =0;i<k;++i){
            auto pair = maxHeap.top();
            maxHeap.pop();
            res.push_back(pair[1]);
        }
        return res;
    }
};

Learned：     

-----------how to declare and use comparator of priority_queue

auto compare = [](const vector<int>& a, const vector<int>& b){return a[1] > b[1];};
<vector<int>, vector<vector<int>>, decltype(compare)> minHeap(compare);