Leetcode 347. 前 K 个高频元素(堆实现)_前k个高频元素最小堆实现报告

347. 前 K 个高频元素(堆实现)
     给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

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

示例 2:

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

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> numCountMap = new HashMap<Integer,Integer>();
        for(int i = 0;i<nums.length;i++){
            numCountMap.put(nums[i],numCountMap.getOrDefault(nums[i],0)+1);
        }

        PriorityQueue<int[]> priority_queue = new PriorityQueue<int[]>(new Comparator<int[]>(){
            public int compare(int[] m,int[] n){
                return m[1]-n[1];
            }
        });

        for(Map.Entry<Integer,Integer> entry : numCountMap.entrySet()){
            int num = entry.getKey(), count = entry.getValue();
            if(priority_queue.size()==k){
                if(priority_queue.peek()[1] < count)
                    {priority_queue.poll();
                    priority_queue.offer(new int[]{num,count});}
            }else{
                priority_queue.offer(new int[]{num,count});
            }  
        }

        int[] output = new int[k];
        for(int i = 0;i<k;++i){
            output[i] = priority_queue.poll()[0];
        }
        return output;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

笔记

1. PriorityQueue优先队列就是最小堆，默认就是最小堆
2. 可以传入实现Comparator接口的实例，记得加泛型。
3. Comparator返回>0 就是代表大于。即，第一个参数大于第二个参数。
4. for(Map.Entry<Integer,Integer> entry : numCountMap.entrySet()) 两个注意：Entry是Map的成员，泛型有一对儿。
5. PriorityQueue三个函数，offer(),peek(),poll()。offer进poll出。