一、题目描述

示例 1:

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

示例 2:

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

提示：

1 <= nums.length <= 10^5 k 的取值范围是 [1, 数组中不相同的元素的个数] 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

二、思路分析

分析做法 之前，我们先理解题意，刚开始我认为就是求元素个素大于等于k的元素有那些嘛，这不是很简单吗，遍历数组放到map中，key为值，value为次数，找到大于等于k的就ok啦！ TMD，根本不是这个意思！题目的意思是 求出前k个高频的元素！简单的说就是按照出现的频率排序，找到前k个！重点是前k个，不是频率大于等于k的元素有那些！XDM！

题目的意思我们知道了，我们分析一下怎么解决！

第一步，还是遍历元素放到map中，key为数组的值，value为值出现的次数 第二步骤，其实就是排序，找到前k个，答案就出来了！ 其实我们可以用优先级队列来进行升序排序，添加元素的时候如果队列中元素个数大于k，把对头踢出即可！ 最后队列就是我们想要的结果！

三、AC代码

class Solution {
          
   
    public int[] topKFrequent(int[] nums, int k) {
          
   
        int[] results = new int[k];

        Map<Integer, Integer> map = new HashMap<>();
        for (int i : nums){
          
   
            map.put(i, map.getOrDefault(i, 0) + 1);
        }

        // 小顶堆，升序排列
        PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>(
            (o1, o2) ->{
          
   
                return o1.getValue() - o2.getValue();
            }
        );

        for (Map.Entry<Integer, Integer> entry : map.entrySet()){
          
   
            queue.offer(entry);
            if (queue.size() > k){
          
   
                queue.poll();
            }
        }

        for (int i = 0; i < k; i++){
          
   
            results[i] = queue.poll().getKey();
        }

        return results;
    }
}

四、总结

优先级队列的使用（PriorityQueue） 前k个高频的元素 **不等于 **元素个素大于等于K的元素

感谢大家的阅读，我是Alson_Code，一个喜欢把简单问题复杂化，把复杂问题简单化的程序猿！ ❤