[C++] Two clean O(nlogk) solutions (map/MinHeap)


  • 0

    Solution 1. Maintain a map<frequency, number(s)> of k elements with 'largest' frequency, each insert and erase operation takes O(logk) time.

        vector<int> topKFrequent(vector<int>& nums, int k) {
            vector<int>res;
            map<int,vector<int>>mp; //use vector here cuz some numbers may have same frequency.
            unordered_map<int,int>hmap;
            for(auto x:nums) hmap[x]++;
            int count=0;
            for(auto x:hmap){
                if(count<k) mp[x.second].push_back(x.first),count++;
                else{
                    mp[x.second].push_back(x.first),count++;
                    count-=mp.begin()->second.size();
                    mp.erase(mp.begin());
                }
            }
            for(auto x:mp) 
                for(auto y:x.second)
                    res.push_back(y);
            return res;
        }
    

    Solution 2. Simply replace the map with a priority_queue(MinHeap),
    top(): O(1)
    pop(): O(2*log(k))
    push() : O(log(k))

    class Solution {
    private:
        struct compare
        {
            bool operator ()(pair<int,int>&p1,pair<int,int>&p2){ return p1.first > p2.first; }
        };
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
            vector<int> res;
            unordered_map<int,int>m;
            priority_queue<pair<int,int>,vector<pair<int,int>>,compare> pq;
            for(auto x:nums) m[x]++;
            for(auto x:m){
                pq.push(make_pair(x.second, x.first));
                if(pq.size()>k) pq.pop();
            }
            while(!pq.empty()) res.push_back(pq.top().second), pq.pop();
            return res;
        }
    };
    

Log in to reply
 

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