C++ 7 lines hashmap priority_queue


  • 1
    B

    use build-in methods, do not re-invent the wheels, like customized comparator.

    class Solution {
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
            unordered_map<int,int>mp;
            for(auto e : nums) mp[e]++;
            priority_queue<pair<int,int>>pq;
            for(auto e : mp) pq.push(make_pair(e.second, e.first));
            vector<int>ans;
            for(int i = 0; i < k; i++, pq.pop()) ans.push_back(pq.top().second);
            return ans;
        }
    };

  • 0

    I think the line to form priority queue "for(auto e : mp) pq.push(make_pair(e.second, e.first));" can be improved.
    Check if pq size is already k and whether the incoming e.second > pq.top().second. If not, no need to push into pq. So we only need to maintain the size of pq up to k.
    The improved algorithm will have O(N log k) cost instead of O(N log N) cost.


  • 0
    B

    @zzg_zzm that is a good point
    To do that we need to change the priority queue to min-heap, and reverse the output vector in the end, which makes the code ugly( in my opinion).


Log in to reply
 

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