【LeetCode热题100】--347.前K个高频元素

347.前K个高频元素

方法：堆

首先遍历整个数组，并使用哈希表记录每个数字出现的次数，并形成一个「出现次数数组」。找出原数组的前 k 个高频元素，就相当于找出「出现次数数组」的前 k 大的值

利用堆的思想：建立一个小顶堆，然后遍历出现次数数组：

• 如果堆的元素小于k，就直接插入堆中

• 如果堆的元素个数等于k，则检查堆顶与当前出现次数的大小，如果堆顶更大，说明至少有k个数字的出现次数比当前值大，故舍弃当前值；否则，就弹出堆顶，并将当前值插入堆中

  遍历完成后，堆中的元素就代表了出现次数数组中前k大的值

class Solution {public int[] topKFrequent(int[] nums, int k) {//使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值Map<Integer,Integer> occurrences = new HashMap<Integer,Integer>();for(int num:nums){occurrences.put(num,occurrences.getOrDefault(num,0) + 1);}//int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数PriorityQueue<int []> 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 : occurrences.entrySet()){int num = entry.getKey(),count = entry.getValue();if(queue.size() == k){if(queue.peek()[1] < count){queue.poll();queue.offer(new int[]{num,count});}}else{queue.offer(new int[]{num,count});}}//取出堆中的元素int[] ret = new int[k];for(int i = 0;i<k;i++){ret[i] = queue.poll()[0];}return ret;}
}