O(nlogk) solution

  • 0

    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){
        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()) {
        return res;

  • 0

    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

    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.