【leetcode hot 100 347】前 K 个高频元素

解法一：用map的value记录key出现的次数，用PriorityQueue构造最小堆。

class Solution {public int[] topKFrequent(int[] nums, int k) {// 把元素放在map中Map<Integer,Integer> map = new HashMap<>();for(int num:nums){if(map.containsKey(num)){map.put(num, map.get(num)+1);}else{map.put(num,1);}}// 构造最小堆PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>(){public int compare(Integer o1, Integer o2){return map.get(o1)-map.get(o2);   // 这里不是o1-o2}});// 向堆中加入元素for(int key:map.keySet()){if(queue.size()<k){// 还可以加入元素queue.offer(key);}else if(map.get(queue.peek())<map.get(key)){// 元素满k个了，但是新加入的元素更多queue.poll();queue.offer(key);}}// 输出int[] result = new int[k];for(int i=0; i<k; i++){result[i] = queue.poll();}return result;}
}

注意：

• 加入元素时，先判断是否到达k个，未到达直接加入；否则，判断是否大于堆顶以决定是否加入。
• 构造最小堆

PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>(){public int compare(Integer o1, Integer o2){return map.get(o1)-map.get(o2);   // 这里不是o1-o2}});