PriorityQueue通过二叉小顶堆实现,可以用一棵完全二叉树表示。
优先队列的作用是能保证每次取出的元素都是队列中权值最小的(Java的优先队列每次取最小元素)。这里牵涉到了大小关系,元素大小的评判可以通过元素本身的自然顺序(natural ordering),也可以通过构造时传入的比较器(Comparator)。
347. 前 K 个高频元素
- 要统计元素出现频率
- 对频率排序
- 找出前K个高频元素
class Solution {
public int[] topKFrequent(int[] nums, int k) {
int[] result = new int[k];
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
// 根据map的value值正序排,相当于一个小顶堆
PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((o1, o2) -> o2.getValue() - o1.getValue());
for (Map.Entry<Integer, Integer> entry : entries) {
queue.offer(entry);
if (queue.size() > k) {
queue.poll();
}
}
for (int i = k - 1; i >= 0; i--) {
result[i] = queue.poll().getKey();
}
return result;
}
}