# [Regards] Summary Of 3 Concise C++ Implementations

• This problem's C++ solutions rely heavily on different data structure design.

First let us check the max-heap (priority_queue) based solutions

class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> map;
for(int num : nums){
map[num]++;
}

vector<int> res;
/** use the priority queue, like the max-heap , we will keep (size-k) smallest elements in the queue**/
/** pair<first, second>: first is frequency,  second is number **/
priority_queue<pair<int,int>> pq;
for(auto it = map.begin(); it != map.end(); it++){
pq.push(make_pair(it->second, it->first));
/** onece the size bigger than size-k, we will pop the value, which is the top k frequent element value **/
if(pq.size() > (int)map.size() - k){
res.push_back(pq.top().second);
pq.pop();
}
}
return res;
}
};

Now let us check the frequency-based array method solutions

class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> m;
for (int  num : nums)
++m[num];
/** as the word frequencies is at most nums.size() **/
vector<vector<int>> buckets(nums.size() + 1);
for (auto p : m)
buckets[p.second].push_back(p.first);
/** we can fetch the top k largest element value from the array **/
vector<int> ans;
for (int i = buckets.size() - 1; i >= 0 && ans.size() < k; --i)
{
for (int num : buckets[i])
{
ans.push_back(num);
if (ans.size() == k)
break;
}
}
return ans;
}
};

The third solution is based on the C++ API : nth_element() to resort the array to left half and right half.

class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> counts;
for (const auto& i : nums)
{
++ counts[i];
}
/** pair : (-frequency, key) **/
vector<pair<int, int>> p;
for (auto it = counts.begin(); it != counts.end(); ++ it)
{
p.emplace_back(-(it->second), it->first);
}
/** nth_element() call will put the  (k-1)-th element on its position,
* the left (k-1) element is smaller than the key, the right bigger **/
nth_element(p.begin(), p.begin() + k - 1, p.end());
vector<int> result;
for (int i = 0; i < k; i++)
{
result.emplace_back(p[i].second);
}
return result;
}
};

• @RainbowSecret
Many thanks for the nth_element solution! I didn't know we got a bonus partial sort in addition to placing the nth element.

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