leetcode347——前K个高频元素——java实现_leetcode 前 k 个高频元素 用最大堆 java

题目要求：

分析：
这种题目又来了，根深蒂固的HashMap思想绝对是呼之欲出。于是不假思索，先用HashMap求出每个数字有几个再说。
求出每个数字的频率之后，我们想要求出第k高的频率的元素，并且时间复杂度必须优于O(nlog n)，那么该如何求呢？
我们应该想到，堆的时间复杂度正好是O(nlog n)，可以用堆来求。而堆是可以利用优先队列PriorityQueue来求的。
我们想要求出第k个频率的数字，那么肯定要堆这些数字出现的次数进行排列，那么优先队列正好是最合适的求法，我们可以让它最先pop出来的是最大值，至于这个排序方法，就是利用匿名内部类，把compare方法给重写一下，这个方法已经用过多次了。
然后就可以取出map中的key值与优先队列中的peek值进行比较了，如果队列没满（队列的容量为k），则将他们加入进来，如果队列满了，并且现在遍历到的这个值大于队列中的peek值，就把队列中最小的给remove掉，然后把这个值给add进去。
最后只要把优先队列中的值给弹出，然后再add到list中去就可以了。

具体代码如下：

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        if(nums == null || nums.length == 0)
            return new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        for(int num : nums) {
            if(!map.containsKey(num)) {
                map.put(num, 1);
            } else {
                map.put(num, map.get(num) + 1);
            }
        }
        // 遍历map，用最小堆保存频率最大的k个元素
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                return map.get(a) - map.get(b);
            }
        });
        //将Map中所有的键存入到set集合中
        for (Integer key : map.keySet()) {
            if (pq.size() < k) {
                pq.add(key);
            } else if (map.get(key) > map.get(pq.peek())) {
                pq.remove();
                pq.add(key);
            }
        }
        // 取出最小堆中的元素
        List<Integer> list = new ArrayList<>();
        while (!pq.isEmpty()) {
            list.add(pq.remove());
        }
        return list;
    }
}
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
32
33
34
35
36