📝 题目描述
题目链接：前 K 个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 示例 1：
输入：nums = [1,1,1,2,2,3], k = 2
输出：[1,2]
示例 2：
输入：nums = [1], k = 1
输出：[1]
示例 3：
输入：nums = [1,2,1,2,1,2,3,1,3,2], k = 2
输出：[1,2]
|
提示：
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4k 的取值范围是 [1, 数组中不相同的元素的个数]题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
💡 解题思路
方法一：桶排序
在长度为 N 的数组中，任何一个元素出现的频率（次数），最少是 1 次，最多也就是 N 次。
既然频率的范围被严格限制在了 [1,N] 这个有限的区间内，我们就不需要通过“比较”来排序（比如堆排序或快排），而是可以直接把频率作为数组的下标（索引）。
步骤：
- 统计频率：使用
unordered_map 统计每个数字出现的次数。
- 构建桶：创建一个长度为 N+1 的数组（为了让下标能取到 N）。这个数组的每一个位置就是一个桶。
- 下标
i：代表元素出现的频率。
- 桶内的内容：存储所有出现频率恰好为
i 的元素。由于可能有多个不同的数字出现频率相同，所以每个桶里需要放一个数组。
- 数字入桶：遍历第一步得到的哈希表，把数字根据它的频率扔进对应的桶里。
- 倒序取数字：因为我们要找的是“频率前
k 高”的元素，而桶的下标越大代表频率越高。所以我们只需从后往前遍历这个桶数组，依次把桶里的数字拿出来放入结果集，直到拿够 k 个为止。
方法二：小顶堆
既然我们只需要前 k 个最高频的元素，我们不需要把所有的 M 个元素都维护在堆里。我们可以维护一个大小固定为 k 的小顶堆。
思路：
- 先用哈希表统计频率。
- 遍历哈希表，将元素逐个放入小顶堆中。
- 如果堆的大小超过了
k，我们就把堆顶元素（也就是当前堆里频率最低的元素）弹出。
- 遍历结束后，留在堆里的
k 个元素，就是我们要找的出现频率前 k 高的元素。
🔧 代码实现
1、桶排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> mp;
for (const auto& num : nums) {
mp[num]++;
}
int n = nums.size();
vector<vector<int>> buckets(n + 1);
for (const auto& p : mp) {
int num = p.first;
int freq = p.second;
buckets[freq].push_back(num);
}
vector<int> res;
for (int i = n; i >= 0 && res.size() < k; --i) {
if (!buckets[i].empty()) {
for (int num : buckets[i]) {
res.push_back(num);
if (res.size() == k) {
return res;
}
}
}
}
return res;
}
};
|
2、小顶堆
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public:
struct compare {
bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
return a.second > b.second;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq;
unordered_map<int, int> mp;
vector<int> res;
for(const auto& num : nums) {
mp[num]++;
}
for(const auto& p : mp) {
if (pq.size() < k) {
pq.push({p.first, p.second});
} else if (p.second > pq.top().second) {
pq.pop();
pq.push({p.first, p.second});
}
}
for(int i = 0; i < k; i++) {
res.push_back(pq.top().first);
pq.pop();
}
return res;
}
};
|
📊 复杂度分析
1、桶排序
- 时间复杂度：O(N)，遍历数组建哈希表 O(N)；遍历哈希表入桶，哈希表中最多有 N 个元素，所以是 O(N)；倒序遍历桶数组，最多遍历 N+1 次桶数组，加上内部取出 k 个元素，总体仍然是 O(N)。
- 空间复杂度：O(N)，哈希表最坏情况占用 O(N)。
2、小顶堆
- 时间复杂度：O(N+Mlogk)，遍历数组统计频率需要 O(N)，同时因为堆的大小一直维持在 k，每次 push 和 pop 的复杂度降到了 O(logk)。
- 空间复杂度：O(M)，哈希表占用 O(M)，堆占用 O(k)，总空间为 O(M)。
🎯 总结
