LeetCode 347 TopK高频元素

前言

这题看到 高频 很容易想到哈希表,然后自定义排序,但是这样的话需要对所有元素进行排序,没有必要

这题可以采用 优先级队列,只需要维护前K个高频元素即可

优先级队列实际上就是一个堆,只是对外的接口只有从队头取元素,从队尾添加元素,看起来就是一个队列

堆是一棵完全二叉树,树中每个节点都不小于(或不大于)左右孩子的值

这题为什么用小顶堆,而不用大顶堆呢?

因为要统计最大前K个元素,只有小顶堆每次将最小的元素弹出,最后堆里剩余的才是前K个高频元素

Java中小顶堆由 PriorityQueue 实现,自定义比较器,默认是小顶堆

理论

下面两张图取自 程序员吴师兄

思路就是堆中存储数组,数组大小为2,索引0位置存储元素,索引1位置存储元素出现次数,自定义排序对索引1位置元素进行比较

最后将堆中剩余元素索引0位置元素放入结果集返回

代码

class Solution {
public int[] topKFrequent(int[] nums, int k) {
int[] result = new int[k];
PriorityQueue<int[]> queue = new PriorityQueue<>((o1,o2) -> (o1[1] - o2[1]));
HashMap<Integer,Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num,map.getOrDefault(num,0) + 1);
}
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
int[] tem = new int[2];
tem[0] = entry.getKey();
tem[1] = entry.getValue();
queue.offer(tem);
if (queue.size() > k){
queue.poll();
}
}
int i = 0;
while(!queue.isEmpty()){
result[i] = queue.poll()[0];
i++;
}
return result;
}
}