Leetcode 347：前K个高频元素

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

示例 1:

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

示例 2:

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

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class title347 {
    public static void main(String[] args) {
        int[] nums={1,1,1,2,2,3};
        int k=2;
        int[] result=topKFrequent(nums,k);
        for (int i=0;i<result.length;i++){
            System.out.print(result[i]+" ");
        }
    }

    public static int[] topKFrequent(int[] nums, int k) {

        int len=nums.length;
        //定义一个map统计频率
        Map<Integer,Integer> map=new HashMap();
        for(int i=0;i<len;i++){
            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
        }

        //Java中的PriorityQueue是一个优先级队列实现,它是基于优先级堆的数据结构（最小堆）
        //输出顺序从小到大

        // 定义一个比较器（Comparator）来定义元素之间的优先级。这个比较器是一个Lambda表达式(pair1, pair2) -> pair1[1] - pair2[1]，它会根据数组中第二个元素的值来比较两个int数组的大小
        //队列中存入元素为键值对，根据第二个元素来排序（频率）
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[1]);

        for (Integer key:map.keySet()) { //小顶堆只需要维持k个元素有序
            if (pq.size() < k) { //小顶堆元素个数小于k个时直接加
                pq.add(new int[]{key, map.get(key)});
            } else {
                if (map.get(key) > pq.peek()[1]) { //当前元素出现次数大于小顶堆的根结点(这k个元素中出现次数最少的那个)
                    pq.poll(); //弹出队头(小顶堆的根结点),即把堆里出现次数最少的那个删除,留下的就是出现次数多的了
                    pq.add(new int[]{key, map.get(key)});
                }
            }
        }
        int[] res=new int[k];
        for (int i = k - 1; i >= 0; i--) { //依次弹出小顶堆,先弹出的是堆的根,出现次数少,后面弹出的出现次数多
            res[i] = pq.poll()[0];
        }
        return res;
    }
}