C++ 36ms solution, using hashmap and sort() or heap


  • 2
    bool compare(pair<int,int> &a, pair<int,int> &b){
        return a.second>b.second;
    }
    
    class Solution {
    public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> cnt;
        vector<int> res;
        for(auto &x:nums) cnt[x]++;
        vector<pair<int,int>> hist;
        for (auto &x:cnt){
            hist.push_back(make_pair(x.first,x.second));
        }
        sort(hist.begin(),hist.end(),compare);
        for (int i=0;i<k;i++){
            res.push_back(hist[i].first);
        }
        return res;
    }
    };
    

    or use heap

    class Solution {
    public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> cnt;
        vector<int> res;
        for(auto &x:nums) cnt[x]++;
        vector<pair<int,int>> hist;
        for (auto &x:cnt){
            hist.push_back(make_pair(x.second,x.first));
        }
        make_heap(hist.begin(),hist.end());
        for (int i=0;i<k;i++){
            res.push_back(hist[0].second);
            pop_heap(hist.begin(),hist.end());
            hist.pop_back();
        }
        return res;
    }
    };

  • 0
    M

    But sorting is O(nlogn)


  • 0

    all right, then using make_heap to do it.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.