347. Top K Frequent Elements - Bucket Sorting
题目详见:347. Top K Frequent Elements
PrioirtyQueue 的解法可以参考类似题 692 的解法:点这里
下面介绍最优解:Bucket Sorting
解法一 Bucket Sorting
思路
一个长度为 n 的数组,一个数字最低的频率为0,最高的频率为n。所以所有可能的频率情况为n。我们可以用一个 长度为 n + 1 的list 数组来记录属于不同频率的所有数字。比如 list[2] = {3, 4} 代表频率为 2 的数字有 3 和 4。
取前 k 个频率最高的元素时,我们仅需从 list 的最后开始遍历取数字,直到取满 k 个数字为止。
代码
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
List<Integer> res = new ArrayList<>();
List<Integer>[] list = new ArrayList[nums.length + 1]; // Frequency array
// 记录每个数字的频率
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
// 记录相应频率下的数字
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
int freq = entry.getValue();
if (list[freq] == null) list[freq] = new ArrayList<>();
list[freq].add(entry.getKey());
}
// 添加 k 个频率最高的数字
for (int i = nums.length; i >= 0 && res.size() < k; i--) {
if (list[i] != null) res.addAll(list[i]);
}
return res;
}
}
复杂度分析
- 时间复杂度 O(n) – 第一个 for 循环 O(n), 第二个 for 循环 O(n), 第三个 for 循环 O(k).
- 空间复杂度 O(n) – bucket 数组储存了所有 n 个数字的频率
本作品采用《CC 协议》,转载必须注明作者和本文链接