题目解析

从数组中找到出现频率前K多的元素

方法一 排序

使用map来获得所有元素的频率,然后排序,找到前k个元素。时间复杂度是O(nlgn) 耗时20ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> counts;
vector<int> result;
vector<pair<int, int>> numsAndCount;
for (int num: nums) {
counts[num]++;
}
for (auto it: counts) {
numsAndCount.push_back(it);
}
sort(numsAndCount.begin(), numsAndCount.end(),
[](auto &a, auto &b){return a.second < b.second;});
for (int i = 0; i < k; i++) {
result.push_back(numsAndCount.back().first);
numsAndCount.pop_back();
}
return result;
}
};

方法二 大根堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> counts;
vector<int> result;
auto cmp = [](auto &a, auto &b){return a.second < b.second;};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> numsAndCount(cmp);
for (int num: nums) {
counts[num]++;
}
for (auto it: counts) {
numsAndCount.push(it);
}

for (int i = 0; i < k; i++) {
result.push_back(numsAndCount.top().first);
numsAndCount.pop();
}
return result;
}
};