347. 前 K 个高频元素（出现频率最多的 k 个元素）

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;
        
    }
}