O(N) solution with quick select (nth_element)


  • 0
    X
    vector<int> topKFrequent(vector<int>& nums, int k) 
        {
            vector<int> res;
            unordered_map<int,int> table;
            for(int val:nums)
                table[val]++;
            vector<pair<int,int>> data;
            for(auto it:table)
                data.push_back({it.second,it.first});
            nth_element(data.begin(),data.begin()+data.size()-k,data.end());
            for(int i=data.size()-k;i<data.size();i++)
                res.push_back(data[i].second);
            return res;
        }
    

Log in to reply
 

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