347. 前 K 个高频元素

一 题目:

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

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

二 思路:

使用小根堆来保留出现次数最多的k个数,堆顶为最多的k个数里的最小值
排序规则采用外部的map进行关联

三 代码:

class Solution {
        public int[] topKFrequent(int[] nums, int k) {
            //统计每个数字的数量
            Map<Integer, Integer> numCount =new HashMap<>();
            for (int num : nums) {
                if (numCount.containsKey(num)){
                    numCount.put(num,numCount.get(num)+1);
                }else {
                    numCount.put(num,1);
                }
            }

            //小根堆,只保留k个数的最大的值,堆顶保留的k个最大的里面的最小值
            final PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.comparingInt(numCount::get));

            //小根堆排序
            numCount.forEach((key, value) -> {
                if (queue.size() < k) {
                    queue.add(key);
                } else if (numCount.get(queue.peek()) < value) {
                    //只保留前k个数字
                    queue.poll();
                    queue.add(key);
                }
            });

            //结果赋值
            final int[] res = new int[k];
            int curr=0;
            while (!queue.isEmpty()){
                res[curr++]=queue.poll();
            }
            return res;
        }
    }