题目描述

解题思路

根据频率大小排序，那么可以使用哈希表来对频率进行统计，在对频率进行排序。
那么问题来了，定义一个大小为k的大顶堆，在每次移动更新大顶堆的时候，每次弹出都把最大的元素弹出去了，那么怎么保留下来前K个高频元素呢。
而且使用大顶堆就要把所有元素都进行排序，那能不能只排序k个元素呢？
所以我们要用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。

/**
         * 使用小顶堆实现
         *
         * @param nums
         * @param k
         * @return
         */
public int[] topKFrequent(int[] nums, int k) {
    int[] res = new int[k];
    HashMap<Integer, Integer> map = new HashMap<>();
    // 将出现的值和频率使用map封装
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
    }
    // 放入集合中方便遍历到队列中
    Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
    // 创建优先队列（小顶堆）
    PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<Map.Entry<Integer, Integer>>((o1, o2) -> {
        return o1.getValue() - o2.getValue();
    });
    // 将map入队
    for (Map.Entry<Integer, Integer> entry : entries) {
        queue.offer(entry);
        // 如果队列中的个数大于k，需要将多余的出队，此时是小顶堆，最小的在队首，所以直接出队即可
        if (queue.size() > k) {
            queue.poll();
        }
    }
    // 取出队列中的所有元素，即为频率前k个元素
    for (int i = 0; i < k; i++) {
        res[i] = queue.poll().getKey();
    }
    return res;
}