C++ Solution With Clean Code O(nlogk)


  • 0
    H
    class Solution {
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
            unordered_map<int, int> m;
            for(int i=0; i<nums.size(); i++)
                m[nums[i]]++;
            
            vector<int> result(k);
    		priority_queue<pair<int, int>,vector<pair<int,int>>, cmp> pq;
            
            for(auto iter = m.begin(); iter != m.end(); iter++)
            {
                
                if(pq.size()>=k && iter->second > pq.top().first)
                {
                    pq.pop();
                    pq.push(make_pair(iter->second, iter->first));
                }
    			else if(pq.size() < k)
    			{
    				pq.push(make_pair(iter->second, iter->first));
    			}
            }
            
            int cnt = k-1;
            while(!pq.empty())
            {
                result[cnt] = pq.top().second;
                pq.pop();
                cnt--;
            }
            
            return result;
            
        }
    
    private:
    	struct cmp
    	{
    		bool operator()(const pair<int,int> &p1, const pair<int,int> &p2)
    		{
    			return p1.first > p2.first;
    		}
    
    	};
    
    };
    

Log in to reply
 

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