​LeetCode刷题实战347：前 K 个高频元素

示例 1:

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

示例 2:

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

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        //将每个数字的出现次数放入HashMap
        Map<Integer, Integer> counts = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            if(counts.containsKey(nums[i])){
                counts.put(nums[i], counts.get(nums[i])+1);
            } else {
                counts.put(nums[i], 1);
            }
        } 

        //建立只有k个元素的最小堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(new Comparator<Integer>(){
            @Override
            public int compare (Integer a, Integer b){
                //要重写compare函数：最小堆中存的是数字，但比较的是数字出现的频率。默认是大顶堆。
                return counts.get(a) - counts.get(b);
            }
        });
        for(Integer key: counts.keySet()){
            if(minHeap.size() < k) {
                minHeap.add(key);
            } else {
                if(counts.get(key) > counts.get(minHeap.peek())){
                    minHeap.remove();
                    minHeap.add(key);
                }
            }
        }

        //输出结果
        int[] result = new int[k];
        for(int i = 0; i < result.length; i++){
            result[i] = minHeap.remove();
        }
        return result;
    }
}