一、题目描述

原文链接：347. 前 K 个高频元素

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

示例 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，一个喜欢把简单问题复杂化，把复杂问题简单化的程序猿！ ❤

湖北工具网