O(n+k) time O(n) space
bucket sort
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> f;
for (int x : nums) {
++f[x];
}
int n = size(nums);
vector<vector<int>> m(n + 1);
for (auto [x, v] : f) {
m[v].push_back(x);
}
vector<int> res;
for (int i = n; i >= 0; --i) {
for (int x : m[i]) {
res.push_back(x);
if (res.size() == k) return res;
}
}
return res;
}
};
|
quick selection
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> m;
for (int x : nums) {
++m[x];
}
vector<pair<int, int>> v(begin(m), end(m));
auto cmp = [](const auto &a, const auto &b){ return a.second > b.second; };
nth_element(begin(v), begin(v) + k, end(v), cmp);
vector<int> res;
for (int i = 0; i < k; ++i) {
res.push_back(v[i].first);
}
return res;
}
};
|