class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        //用map集合存储每个元素以及其出现的次数，但是如何将其进行排序就很难了。
        //可以使用大根堆实现。
        // 对于堆（使用PriorityQueue实现）：从队头到队尾按从小到大排就是最小堆（小顶堆），
        //                             从队头到队尾按从大到小排就是最大堆（大顶堆）--->队头元素相当于堆的根节点
        //1.先定义map存储元素以及其出现的次数
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        //2.定义一个优先队列，优先队列默认是小顶堆，所以需要定义一个比较器，比较器中定义的是升序排序
        // 在优先队列中存储二元组(num, cnt),cnt表示元素值num在数组中的出现次数
        // 出现次数按从队头到队尾的顺序是从大到小排,出现次数最多的在队头(相当于大顶堆)
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o2[1] - o1[1]);
        //3.遍历map集合，将其加入到优先队列中
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            pq.add(new int[]{entry.getKey(), entry.getValue()});
        }
        //4.依次从队头弹出k个,就是出现频率前k高的元素
        int[] ans = new int[k];
        //    每次调用 pq.poll() 都会移除并返回当前队列中频率最高的元素（以 [num, cnt] 的形式存储），并通过 [0] 提取 num 值。
        for (int i = 0; i < k; i++) { 
            ans[i] = pq.poll()[0];
        }
        return ans;
    }
}