C++ 19ms Priority queue pair solution


  • 1
    X

    Here is my solution. But I think the runtime is O(klog(n)). Because I popped the priority queue k times. Each pop of a priority queue take log(n). Is that right?

    //https://leetcode.com/problems/top-k-frequent-elements/description/
    
    class Solution {
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
            unordered_map<int, int> map; // value -> frequency
            priority_queue< pair<int,int> > q; // /frequency -> value ; max priority queue
            for(int x : nums) { // record the frequency in the map
                map[x]++;
            }
            vector<int> output;
            for(auto x : map){
                q.push(make_pair(x.second, x.first)); // reverse key and value pair
            }
            while(q.size() && k){ 
                output.push_back(q.top().second); // queue: frequency -> value
                k--;
                q.pop();
            }
            return output;
        }
    };
    

  • 0
    M

    @x65han
    Thanks for the solution! I tend to forget about priority queues. I'm glad you've reminded me :-)

    Yes, the O(log(n)) look up time is correct. However the code is a pure N log(N) because of the map.size() inserts into the queue :(.

    I think this could be changed by using one of the range constructors for the priority_queue and supplying an explicit compare function instead of reversing the pair values. In that case it would be an O(N) construction cost -- basically the cost of making a heap.

    Here is a version:

    
        vector<int> topKFrequent_next(vector<int> nums, int k) {
            unordered_map<int, int> freqs;
            for (auto num : nums)
                freqs[num]++;
    
            // shorthand
            using elt = pair<int, int>;
    
            auto cmp = [](elt lhs, elt rhs)
            { return lhs.second < rhs.second; };
    
            // See http://en.cppreference.com/w/cpp/container/priority_queue/priority_queue
            priority_queue<elt, vector<elt>, decltype(cmp)> queue(begin(freqs), end(freqs), cmp);
    
            vector<int> res(k);
            for (int i = 0; i < k; ++i) {
                res[i] = queue.top().first;
                queue.pop();
            }
    
            return res;
        }
    

Log in to reply
 

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