​​​​​​347. 前 K 个高频元素

 

        本题还是细节处理比较多，我不太熟悉小顶堆大顶堆，这个题花了一个多小时在搞基础，具体细节在代码部分。

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i ++) {
            //getOrDefault():如果map中没有nums[i]，则返回值0
            map.put(nums[i], map.getOrDefault(nums[i],0) + 1);
        }
        // int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
        //(e1, e2) -> e2.getValue() - e1.getValue()
        //这一步是制造小顶堆，m是先入的值，n是后入的值
        //如果n<m，return false，则需要交换n和m位置，m放堆顶，则为小顶堆，反之为大顶堆。
        //优先队列用比较器改变小顶堆大顶堆。
        //优先队列中存放的是数组int[]，数组中0位置是map的key，1位置是map的value。
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>(){
            public int compare(int[] m, int[] n) {
                return m[1] - n[1];
            }
        });
        //entrys是java中Map键值对的一对映射，entrySet是Map的键值对集合
        for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
            int num = entry.getKey(),count = entry.getValue();
            if (queue.size() == k) {
                //小顶堆，所以当前队头储存的是当前放入元素中出现次数最少的。
                //如果当前队头存放的数组的第二个位置（即当前存放的最低次数的数字）的值小于当前准备放入的值，则将队头元素移出，放入新数组。
                //queue.peek()[1]相当于int[1]
                if (queue.peek()[1] < count) {
                    queue.poll();
                    queue.offer(new int[]{num, count});
                }
            } else {
                queue.offer(new int[]{num, count});
            }
        }
        int[] ret = new int[k];
        //这一步是把int[0]的值拿出来放入ret数组，这就是最终结果，int[0]就是出现前k高的元素
        for (int i = 0; i < k; ++i) {
            ret[i] = queue.poll()[0];
        }
        return ret;
    }
}