力扣刷题笔记347

力扣刷题笔记347 347.前 K 个高频元素 简介：

给你一个整数数组 nums和一个整数k，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

题解：

这道题的第一步是记录每个数字的出现次数，这一步十分简单
我们可以采用一个Map来存储数字和他的出现次数
然后就是比较出现次数的大小，确立前K个高频元素，这一步也是最重要的一步。
我们可以采用快排的方式对数字的出现次数进行排序然后去前k个元素（其他排序也行）
在此我提供一种借助小顶堆的方法来实现

类似这种
我们可以借助java中自带的优先级队列PriorityQueue来实现小顶堆
根据PriorityQueue的选择器，设置按出现次数的大小，从大到小入
队即可。

代码：

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
     // map 记录 key num value个数
        Map map = new HashMap<>();
        for (int num : nums){
            map.put(num, map.getOrDefault(num,0)+1);
        }
        // 将map放入set中
        Set> entries = map.entrySet();
        // 放 PriorityQueue优先级队列
        PriorityQueue> q = new PriorityQueue<>(
                (n1,n2)-> n1.getValue()- n2.getValue());
        for (Map.Entry entry : entries) {
            q.offer(entry);
            if(q.size()>k){
                q.poll();
            }
        }
        int []res = new int[k];
        for (int i = k-1; i >= 0; i--){
            res[i] = q.poll().getKey();
        }
        return res;
    }
}