O(n*lgk) hash + minHeap


  • 0
    F
    class Solution {
    public:
        struct comp
        {
            bool operator()(const pair<int, int> &l, const pair<int, int> &r)
            {
                return l.second > r.second;
            }
        };
    
        vector<int> topKFrequent(vector<int>& nums, int k) {
            unordered_map<int, int> map;
            
            for(int i = 0; i < nums.size(); ++i)
            {
                if(map.find(nums[i]) != map.end())
                {
                    ++map[nums[i]];
                }
                else
                {
                    map[nums[i]] = 1;
                }
            }
            
            priority_queue<pair<int,int>, vector<pair<int,int>>, comp> hp;
            
            for(auto iter = map.begin(); iter != map.end(); ++iter)
            {
                hp.push(make_pair(iter->first, iter->second));
                if(hp.size() > k) hp.pop();
            }
            
            vector<int> result;
            while(!hp.empty())
            {
                result.push_back(hp.top().first);
                hp.pop();
            }
            
            
            return result;
        }
    };

Log in to reply
 

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