力扣【347. 前 K 个高频元素】Java题解（堆）

TopK问题，我们直接上堆。
首先遍历一次然后把各个数字的出现频率存放在哈希表中便于后面堆的操作。
因为是出现频率前 k 高，所以用小顶堆，当我们遍历的频率值大于堆顶值时就可以替换堆顶。

代码：

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int num:nums){
            map.put(num,map.getOrDefault(num,0)+1);
        }
        PriorityQueue<int[]> que = new PriorityQueue<int[]>((a,b)->{
            return a[1]-b[1];
        });
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            if(que.size() < k) {
                que.offer(new int[]{entry.getKey(),entry.getValue()});
                continue;
            }
            if(que.peek()[1] < entry.getValue()){
                que.poll();
                que.offer(new int[]{entry.getKey(),entry.getValue()});
            }

        }
        int[] res = new int[k];
        int i =0;
        for(int[] arr:que){
            res[i++] = arr[0];
        }
        return res;
    }
}

扩展：
1.获取map的所有元素（键值对），map.enreySet()，类型是Map.Entry<T1,T2>
获取键值对的键entry.getKey()，获取值entry.getValue()

2.Java堆常用函数：

• offer(E e) 元素入堆
• peek() 返回堆顶元素
• poll() 堆顶元素出堆