题目
题目来源leetcode
leetcode地址：347. 前 K 个高频元素，难度：中等。
题目描述(摘自leetcode)：
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 示例 1: 输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例 2: 输入: nums = [1], k = 1 输出: [1] 提示： 1 <= nums.length <= 105 k 的取值范围是 [1, 数组中不相同的元素的个数] 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
本地调试代码：
class Solution { public int[] topKFrequent(int[] nums, int k) { ... } public static void main(String[] args) { int[] nums = new int[]{1,1,1,2,2,3}; System.out.println(Arrays.toString(new Solution().topKFrequent(nums,2))); } }
题解
NO1：哈希表+优先队列
思路： 先使用哈希表来进行统计对应值的频率，之后创建一个优先队列设置一个从小到大排序的比较器，每次插入一组key、value后，判断当前的容量是否>k个，若是大于了直接将队头的出队(在队列里频率最小的)，最终遍历取出队列中的k组数据即可。
代码：
public int[] topKFrequent(int[] nums, int k) { //使用map来进行统计指定指定数的频率，key为num，value为频率 Map<Integer,Integer> map = new HashMap<>(); for (int num : nums) { map.put(num,map.getOrDefault(num,0)+1); } Set<Map.Entry<Integer, Integer>> entries = map.entrySet(); //创建优先队列，传入Comparator匿名接口类，插入队列的元素从小到达排列 PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((o1,o2)->o1.getValue()-o2.getValue()); for (Map.Entry<Integer, Integer> entry : entries) { queue.offer(entry); if(queue.size() > k){ //一旦队列中的数量大于k，直接将频率最小的出队(队头) queue.poll(); } } //最终取出对应的最大k值 int[] maxNums = new int[k]; for (int i = k-1; i >=0 ; i--) { maxNums[i] = queue.poll().getKey(); } return maxNums; }
NO2：排序遍历+优先队列
思路：首先进行从小到大排序，之后对整个数组进行遍历，以[i]!=[i-1]来作为存储到队列的依据，队列按照从大到小排序，每次入队后判断是否>k个，若是大于出队。最终遍历k个即可获取到前k个高频元素。
代码：
public int[] topKFrequent(int[] nums, int k) { Arrays.sort(nums); //优先队列，按照频率从小到大排列(Comparator返回值为负数就从小到大排列，若是正数从大到小) PriorityQueue<int[]> queue = new PriorityQueue<int[]>((o1, o2) -> o1[1] - o2[1]); //对数组进行遍历操作 int i = 1; int j = 1; for (; i < nums.length; i++) { if (nums[i] == nums[i - 1]) { j++; } else { queue.offer(new int[]{nums[i - 1], j}); if (queue.size() > k) { //一旦大于原本k个数量就进行移除 queue.poll(); } j = 1; } } queue.offer(new int[]{nums[i - 1], j}); if (queue.size() > k) { queue.poll(); } //从队列中取出k个 int[] maxNums = new int[k]; for (int l = 0; l < k; l++) { maxNums[l] = queue.poll()[0]; } return maxNums; }
