前K个高频元素

347. 前 K 个高频元素

给定一个非空的整数数组,返回其中出现频率前K高的元素。

对于TopK问题,堆排序是最明显的解法,但这题其实有时间度复杂度更低的解法,通过桶排序来解题:我们首先用HashMap保存每个数字出现次数,再遍历整个map将数字放入代表数字出现次数的桶中,倒序遍历桶就可以得到TopK的高频元素。最后的时间复杂度维持在O(n)。

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
class Solution {
public int[] topKFrequent(int[] nums, int k) {
//用HashMap保存每个数字出现次数
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i])) {
map.put(nums[i], map.get(nums[i]) + 1);
} else {
map.put(nums[i], 1);
}
}
//使用桶来保存这些数字
List<Integer>[] bucket = new ArrayList[nums.length + 1];
for (int num : map.keySet()) {
if (bucket[map.get(num)] == null) {
bucket[map.get(num)] = new ArrayList<>();
}
bucket[map.get(num)].add(num);
}
//反向遍历桶,提出倒数k个元素
int[] result = new int[k];
int ans = 0;
for (int i = bucket.length - 1; i >= 0 && ans < k; i--) {
//这里只需要在外层循环判断ans是否小于K,因为题目已经说明数组中前 k 个高频元素的集合是唯一的
if (bucket[i] != null) {
for (int j = 0; j < bucket[i].size(); j++) {
result[ans++] = bucket[i].get(j);
}
}
}
return result;
}

}