# 3 ways to solve this problem

• using heap

``````class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
unordered_map<int, int> cnt;
for (auto num : nums) cnt[num]++;
for (auto kv : cnt) {
pq.push({kv.second, kv.first});
while (pq.size() > k) pq.pop();
}
vector<int> res;
while (!pq.empty()) {
res.push_back(pq.top().second);
pq.pop();
}
return res;
}
};
``````

using selection algorithm

``````class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
vector<int> res;
if (!nums.size()) return res;
unordered_map<int, int> cnt;
for (auto num : nums) cnt[num]++;
vector<pair<int, int>> num_with_cnt;
for (auto kv : cnt) {
num_with_cnt.push_back({kv.first, kv.second});
}
kselection(num_with_cnt, 0, num_with_cnt.size()-1, k);
for (int i = 0; i < k && i < num_with_cnt.size(); ++i) {
res.push_back(num_with_cnt[i].first);
}
return res;
}

void kselection(vector<pair<int, int>>& data, int start, int end, int k) {

if (start >= end) return;
auto pv = data[end];
int i = start;
int j = start;
while (i < end) {
if (data[i].second > pv.second) {
swap(data[i++], data[j++]);
} else {
++i;
}
}
swap(data[j], data[end]);
int num = j - start + 1;
if (num == k) return;
else if (num < k) {
kselection(data, j + 1, end, k - num);
} else {
kselection(data, start, j - 1, k);
}
}
};
``````

using bucket sort

``````class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
vector<int> res;
if (!nums.size()) return res;
unordered_map<int, int> cnt;
for (auto num : nums) cnt[num]++;
vector<vector<int>> bucket(nums.size() + 1);
for (auto kv : cnt) {
bucket[kv.second].push_back(kv.first);
}

for (int i = bucket.size() - 1; i >= 0; --i) {
for (int j = 0; j < bucket[i].size(); ++j){
res.push_back(bucket[i][j]);
if (res.size() == k) return res;
}
}

return res;
}
};``````

• { 1st will run in n * log(n) for input like [1, 2, ..., n] } my bad - you're keeping the queue at size k

2nd - since pivot is always last element - can run in n^2 in worst case

3rd is neat

• another better bucket sort way

``````class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> mp;
vector<int> ans;
int max_frequence = 0,last;
for(auto x:nums)
max_frequence = max(++mp[x],max_frequence);
vector<int> frequence(max_frequence + 1);
for(auto x:mp)
frequence[x.second]++;
for(int i = max_frequence; k > 0; i--)
k -= frequence[last=i];
for(auto x:mp)
if(x.second >last ||(x.second == last && ++k > 0))
ans.push_back(x.first);
return ans;
}
};``````

• Thank you for the nice solutions. But I think the first and the second would be O(nlogn).

• actually I think we don't need that part "&& ++k > 0" inside this if statement:

if(x.second >last ||(x.second == last && ++k > 0))

what's the reason for that?

• for corner case like [1,1,2,2,3,3] 2

• interestingly after removing "&& ++k > 0", still got AC from OJ

• -_-|| ,The test cases are weak....

• @robin8 What is the running time and space complexity for the bucket sort solution i.e. the 3rd one?

• It looks like kselection can be impemened using std::nth_element:

``````auto byCount = [](const pair<int,int>& a, const pair<int,int>&b) { return a.second > b.second; };
nth_element(num_with_cnt.begin(), num_with_cnt.begin()+k, num_with_cnt.end(), byCount);
``````

• @sculd I think the first solution is O(n logk).
step 1 counting using unordered_map takes O(n).
step 2 partial sorting using priority_queue takes O(n log k);
step 3 transforming into a sorted vector takes O(k).
so, overall it is O(n logk).

Additionally, I think there's problem with step 3.
Popped element should be put into vector res in a reversed order instead of that in the written code, or else the most frequent element will be the last one in the vector res.

• This post is deleted!

• 厉害了
厉害了
厉害了
厉害了
厉害了

• The time complextiy of your kselect function is O(logn) or O(logk)?

• The code is quite clear and beautiful.
But maybe the calling of recursion part in selection algorithm :

`````` if (num == k) return;
else if (num < k) {
kselection(data, j + 1, end, k - num);
} else {
kselection(data, start, j - 1, k);
}
``````

can be written in

``````if(k == j)return;
if(k > j)kselection(data, j + 1, end, k);
else kselection(data, start, j - 1, k);
``````

which looks a little bit cleaner.

• Does the result from the second solution keep the order of the frequency?

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