O(nlogk) solution


  • 0
    Y

    I am wondering why people don't share out the O(nlogk) solution. Keep a max heap has size K. This in principle will be closed to O(n) since logk is a constant.

    using Pair = pair<int, int>;
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> map;
        for(int num : nums){
            map[num]++;
        }
    
        vector<int> res;
        // pair<first, second>: first is frequency,  second is number
        priority_queue<Pair, vector<Pair>, greater<Pair>> pq; 
        for(auto it = map.begin(); it != map.end(); it++){
            pq.push(make_pair(it->second, it->first));
            if(pq.size() > k) pq.pop();
        }
        
        while(!pq.empty()) {
            res.push_back(pq.top().second);
            pq.pop();
        }
            
        return res;
    }

  • 0
    T

    Since unordered_map insert operation is not always constant(its O(n) worst case) you cannot argue that your solution runs in O(nlogk).


  • 0
    Y

    There is no sense to argue the "worst case" runtime of the insertion operation of unordered_map. When using a hash table, often times people cares and talks about amortized run time. The insertion operation has an amortized runtime of O(1). In practice, to improve performance, you can always reserve a size for the hashmap to reduce collison and rehashing.


Log in to reply
 

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