# C++ 19ms Priority queue pair solution

• 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;
}
};
``````

• @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;
}
``````

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