力扣347 前K个高频元素

标签：pq int 元素 力扣 347 entry new 高频 小顶

题目：

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例：

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

思路：

这道题目主要涉及三块内容：

（1）要统计元素出现频率：使用map来进行统计

（2）对频率排序：使用一种 容器适配器就是优先级队列（就是一个披着队列外衣的堆）

（3）找出前K个高频元素：用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();//key为数组元素值,val为对应出现次数
        //1.统计元素出现频率
        for(int num:nums){
            map.put(num,map.getOrDefault(num,0)+1);//遍历，存在num，则次数+1
            //Map.getOrDefault(key，默认值);如果在Map中存在key,对应的value。如果不存在，返回默认值
        }

        //2.对频率排序
　　　　　//出现次数按从队头到队尾的顺序是从小到大排,出现次数最低的在队头(相当于小顶堆)
        PriorityQueue<int[]> pq=new PriorityQueue<>((pair1,pair2)->pair1[1]-pair2[1]);
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            if(pq.size()<k){//小顶堆元素个数小于k时直接加
                pq.add(new int[]{entry.getKey(),entry.getValue()});
            }else{
                if(entry.getValue()>pq.peek()[1]){//当前元素出现次数大于小顶堆的根结点
                    pq.poll();//弹出队头
                    pq.add(new int[]{entry.getKey(),entry.getValue()});
                }
            }
        }

        //3.找出前K个高频元素
        int[] ans=new int[k];
        for(int i=k-1;i>=0;i--){
            ans[i]=pq.poll()[0];
        }
        return ans;
    }
}

 tips:

PriorityQueue<Integer> heap = new PriorityQueue<>(
    (w1, w2) -> w2 - w1    // 第二个参数减第一个是大顶堆
);

 

 

 

 

标签：pq,int,元素,力扣,347,entry,new,高频,小顶
From： https://www.cnblogs.com/cjhtxdy/p/17023703.html