C++ unordered_map and priority_queue(min_heap) nlog(k)


  • 1
    G
    class Solution {
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
            unordered_map<int, int> mp;
            for(int i =0;i<nums.size();i++)
                mp[nums[i]]++;
            //use min_heap instead of max heap
            priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> myqueue;
            for(auto i : mp)
            {
                myqueue.push({i.second, i.first});
                //keep the size of the heap to be k
                if(myqueue.size()==k+1)
                    myqueue.pop();
            }
            vector<int> res;
            while(!myqueue.empty())
            {
                res.push_back(myqueue.top().second);
                myqueue.pop();
            }
            return res;
        }
    };
    

Log in to reply
 

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