力扣347. 前 K 个高频元素

本文主要是介绍力扣347. 前 K 个高频元素，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：记录元素出现的次数用map；
要维护前k个元素，不至于把所有元素都排序再取前k个，而是新建一个堆，用小根堆存放前k个最大的数。
为什么是小根堆？因为堆每次出数据时只出堆顶，每次把当前最小的堆顶排出去
，把更大的换进来，到最后只会剩下几个最大的元素。
堆的排序复杂度是 log(K)，所以整体是 n*long(K);

class Solution {public int[] topKFrequent(int[] nums, int k) {Map<Integer,Integer> map = new HashMap<>();//元素和次数 放入mapfor(int i : nums){map.put(i, map.getOrDefault(i,0)+1);}//int[] 里面只放2两个值k-v，用来代替map的元素PriorityQueue<int[]> xiaoDui = new PriorityQueue<>((nums1,nums2)->nums1[1]-nums2[1]);//小根堆//遍历map里的元素，维护一个K个元素的小根堆，里面放的是大数for(Map.Entry<Integer,Integer> item : map.entrySet()) {if(xiaoDui.size()<k){xiaoDui.add(new int[] {item.getKey(),item.getValue()});}else{//堆顶元素小时，出堆顶，入新元素if(xiaoDui.peek()[1]<item.getValue()) {xiaoDui.poll();xiaoDui.add(new int[] {item.getKey(),item.getValue()});}}}//把key取出来返回int[] ans = new int[k];for(int i=0;i<k;i++){ans[i] = xiaoDui.poll()[0];}return ans;}
}

这篇关于力扣347. 前 K 个高频元素的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---