347. 前 K 个高频元素

题目要求解题思路代码

题目要求

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

解题思路

这题首先有一个坑：题目给你的方法是List< Integer>但是题目要求的返回类型是int[] 所以第一步，就是要把方法的类型换成int[]。 然后这个问题是个TopK问题，所以可以考虑用堆来解决。 定义一个最大堆（用小顶堆实现）。当堆中元素达到K个后，再放入的元素与堆顶元素进行比较，如果小于堆顶元素，那么就将它丢弃。如果大于堆顶元素，就将它插入堆，并且丢弃掉之前的堆顶元素

TopK Elements 问题，简单来说就是在一堆数据里面找到前 K 小（当然也可以是前 K 大）的数。可以维护一个大小为 K 的最小堆(这里的堆和JVM中的堆是两个概念)，最小堆中的元素就是最小元素。最小堆需要使用大顶堆来实现，大顶堆表示堆顶元素是堆中最大元素。这是因为我们要得到 k 个最小的元素，因此当遍历到一个新的元素时，需要知道这个新元素是否比堆中最大的元素更小，更小的话就把堆中最大元素去除，并将新元素添加到堆中，再重新排序。

堆也可以用于求解 Kth Element 问题,也就是第 K 个元素的问题，得到了大小为 k 的最小堆之后，因为使用了大顶堆来实现，因此堆顶元素就是第 k 大的元素。

代码

class Solution { public int[] topKFrequent(int[] nums, int k) { if (nums == null) { return null; } // 首先统计不同的元素出现的次数。 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); } } // 遍历map，用最小堆保存频率最大的K个元素 PriorityQueue<Integer> pq=new PriorityQueue<>(new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return map.get(o1)-map.get(o2);//定义最小堆 } }); for (Integer key:map.keySet()){//keySet()方法获取所有的key值 if (pq.size()<k){//如果最小堆的元素个数还没到k个，那么直接往里面添加元素即可 pq.add(key); } //如果最小堆的元素已经超过了k，则将即将放入的元素与堆顶元素比较，如果它大就将堆顶元素弹出，放入它，如果它小，则被丢弃 else if(map.get(key)>map.get(pq.peek())){//peek()函数返回栈顶的元素，但不弹出该栈顶元素。 pq.remove();//在队头删除元素，并返回，再调整堆结构 pq.add(key); } } // 取出最小堆中的元素 List<Integer> res = new ArrayList<>(); while (!pq.isEmpty()) { res.add(pq.remove()); } int[] arr = res.stream().mapToInt(Integer::valueOf).toArray(); return arr; } }