优先队列/最大堆

优先队列/最大堆

347.前k个高频元素

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

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

示例 2:

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

解法一

将EntrySet转为List

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length;i++){
            if(map.containsKey(nums[i])){
                map.put(nums[i],map.get(nums[i])+1);
            }else{
                map.put(nums[i],1);
            }
        }
        //将map的entrySet转为ArrayList
        ArrayList<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
        Collections.sort(list,(a,b)->b.getValue() - a.getValue());
        int[] res = new int[k];
        for(int i = 0; i < k;i++){
            res[i] = list.get(i).getKey();
        }
        return res;
    }
}

解法二

优先队列, 队列中存放key, 比较规则为value大的放在前面

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length;i++){
            //如果map种不含有指定的key， 就返回0
            int times = map.getOrDefault(nums[i],0);
            map.put(nums[i],times+1);
        }
        //使用优先队列（最大堆）,按照key的value从大到小排序
        Queue<Integer> q = new PriorityQueue<>((a,b)->map.get(b)-map.get(a));
        for(Integer key:map.keySet()){
            q.add(key);
        }
        int[] res = new int[k];
        for(int i = 0; i < k;i++){
            res[i] = q.poll();
        }
        return res;
    }
}