题目
题目
思路
暴力排序
排序最优是O(nlogn)，不满足要求
最小堆
- 借助哈希表来建立数字和其出现次数的映射，遍历一遍数组统计元素的频率
- 维护一个元素数目为k的最小堆
- 每次都将新的元素与堆顶元素（堆中频率最小的元素）进行比较
- 如果新的元素的频率比堆顶元素大，则弹出堆顶端的元素，将新的元素添加到堆中
- 最终，堆中的k个元素即为前k个高频元素
时间复杂度为O(nlogk)
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
// pq不指定Comparator时默认为最小堆
Queue<Integer> pq = new PriorityQueue<>(k, new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b){
return map.get(a) - map.get(b);
}
});
for (int key : map.keySet()) {
if (pq.size() < k) {
pq.add(key);
} else if (map.get(key) > map.get(pq.peek())) {
pq.remove();
pq.add(key);
}
}
int[] res = new int[k];
int i = 0;
while(!pq.isEmpty()) {
res[i] = pq.remove();
i++;
}
return res;
}
}
桶排序法
首先使用哈希表统计频率，然后创建一个数组，将频率作为数组下标，对于出现频率不同的数字集合，存入对应的数组下标
时间复杂度为O(n)
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
int[] res = new int[k];
Map<Integer, Integer> map = new HashMap();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
// 桶排序
List<Integer>[] list = new List[nums.length + 1];
for (int key : map.keySet()) {
int i = map.get(key);
if (list[i] == null) {
list[i] = new ArrayList<>();
}
list[i].add(key);
}
int j = 0;
for (int i = list.length - 1; i >= 0 && j < k; i--) {
if (list[i] == null) {
continue;
}
for (int num : list[i]) {
res[j] = num;
j++;
}
}
return res;
}
}
