前 K 个高频元素
约 874 字大约 3 分钟
前 K 个高频元素
写法
/*Comparator接口说明:
* 返回负数,形参中第一个参数排在前面;返回正数,形参中第二个参数排在前面
* 对于队列:排在前面意味着往队头靠
* 对于堆(使用PriorityQueue实现):从队头到队尾按从小到大排就是最小堆(小顶堆),
* 从队头到队尾按从大到小排就是最大堆(大顶堆)--->队头元素相当于堆的根节点
* */
class Solution {
//解法1:基于大顶堆实现
public int[] topKFrequent1(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();//key为数组元素值,val为对应出现次数
for(int num:nums){
map.put(num,map.getOrDefault(num,0)+1);
}
//在优先队列中存储二元组(num,cnt),cnt表示元素值num在数组中的出现次数
//出现次数按从队头到队尾的顺序是从大到小排,出现次数最多的在队头(相当于大顶堆)
PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2)->pair2[1]-pair1[1]);
for(Map.Entry<Integer,Integer> entry:map.entrySet()){//大顶堆需要对所有元素进行排序
pq.add(new int[]{entry.getKey(),entry.getValue()});
}
int[] ans = new int[k];
for(int i=0;i<k;i++){//依次从队头弹出k个,就是出现频率前k高的元素
ans[i] = pq.poll()[0];
}
return ans;
}
//解法2:基于小顶堆实现
public int[] topKFrequent2(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();//key为数组元素值,val为对应出现次数
for(int num:nums){
map.put(num,map.getOrDefault(num,0)+1);
}
//在优先队列中存储二元组(num,cnt),cnt表示元素值num在数组中的出现次数
//出现次数按从队头到队尾的顺序是从小到大排,出现次数最低的在队头(相当于小顶堆)
PriorityQueue<int[]> pq = new PriorityQueue<>((pair1,pair2)->pair1[1]-pair2[1]);
for(Map.Entry<Integer,Integer> entry:map.entrySet()){//小顶堆只需要维持k个元素有序
if(pq.size()<k){//小顶堆元素个数小于k个时直接加
pq.add(new int[]{entry.getKey(),entry.getValue()});
}else{
if(entry.getValue()>pq.peek()[1]){//当前元素出现次数大于小顶堆的根结点(这k个元素中出现次数最少的那个)
pq.poll();//弹出队头(小顶堆的根结点),即把堆里出现次数最少的那个删除,留下的就是出现次数多的了
pq.add(new int[]{entry.getKey(),entry.getValue()});
}
}
}
int[] ans = new int[k];
for(int i=k-1;i>=0;i--){//依次弹出小顶堆,先弹出的是堆的根,出现次数少,后面弹出的出现次数多
ans[i] = pq.poll()[0];
}
return ans;
}
}
class Solution {
public int[] topKFrequent(int[] nums, int k) {
// 优先级队列,为了避免复杂 api 操作,pq 存储数组
// lambda 表达式设置优先级队列从大到小存储 o1 - o2 为从小到大,o2 - o1 反之
PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
int[] res = new int[k]; // 答案数组为 k 个元素
Map<Integer, Integer> map = new HashMap<>(); // 记录元素出现次数
for(int num : nums) map.put(num, map.getOrDefault(num, 0) + 1);
for(var x : map.entrySet()) { // entrySet 获取 k-v Set 集合
// 将 kv 转化成数组
int[] tmp = new int[2];
tmp[0] = x.getKey();
tmp[1] = x.getValue();
pq.offer(tmp);
// 下面的代码是根据小根堆实现的,我只保留优先队列的最后的k个,只要超出了k我就将最小的弹出,剩余的k个就是答案
if(pq.size() > k) {
pq.poll();
}
}
for(int i = 0; i < k; i ++) {
res[i] = pq.poll()[0]; // 获取优先队列里的元素
}
return res;
}
}