- 前 K 个高频元素(堆实现)
给定一个非空的整数数组,返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer,Integer> numCountMap = new HashMap<Integer,Integer>();
for(int i = 0;i<nums.length;i++){
numCountMap.put(nums[i],numCountMap.getOrDefault(nums[i],0)+1);
}
PriorityQueue<int[]> priority_queue = new PriorityQueue<int[]>(new Comparator<int[]>(){
public int compare(int[] m,int[] n){
return m[1]-n[1];
}
});
for(Map.Entry<Integer,Integer> entry : numCountMap.entrySet()){
int num = entry.getKey(), count = entry.getValue();
if(priority_queue.size()==k){
if(priority_queue.peek()[1] < count)
{priority_queue.poll();
priority_queue.offer(new int[]{num,count});}
}else{
priority_queue.offer(new int[]{num,count});
}
}
int[] output = new int[k];
for(int i = 0;i<k;++i){
output[i] = priority_queue.poll()[0];
}
return output;
}
}
笔记
- PriorityQueue优先队列就是最小堆,默认就是最小堆
- 可以传入实现Comparator接口的实例,记得加泛型。
- Comparator返回>0 就是代表大于。即,第一个参数大于第二个参数。
- for(Map.Entry<Integer,Integer> entry : numCountMap.entrySet()) 两个注意:Entry是Map的成员,泛型有一对儿。
- PriorityQueue三个函数,offer(),peek(),poll()。offer进poll出。