JAVA练习348- 前 K 个高频元素

题目概览给你一个整数数组nums和一个整数k请你返回其中出现频率前k高的元素。你可以按任意顺序返回答案。示例 1输入nums [1,1,1,2,2,3], k 2输出[1,2]示例 2输入nums [1], k 1输出[1]示例 3输入nums [1,2,1,2,1,2,3,1,3,2], k 2输出[1,2]提示1 nums.length 10^5-10^4 nums[i] 10^4k的取值范围是[1, 数组中不相同的元素的个数]题目数据保证答案唯一换句话说数组中前k个高频元素的集合是唯一的进阶你所设计算法的时间复杂度必须优于O(n log n)其中n是数组大小。来源347. 前 K 个高频元素 - 力扣LeetCode解题分析方法哈希 堆每个数字出现次数可以先遍历一次用哈希表存储。由于对出现次数进行排序的话时间复杂度会达到 nlogn因此我们可以用通过堆来实现通过实现一个最小堆堆顶只放出现次数最小的元素则当堆大小小于 k 时入堆当堆大小等于 k 时比较当前元素与堆顶元素大小若当前元素大则将栈顶元素出栈入当前元素否则忽略时间复杂度O(nlogk) ( k 为优先队列的大小空间复杂度O(nlogk)class Solution { public int[] topKFrequent(int[] nums, int k) { final MapInteger, Integer map new HashMap(); for (int num: nums) { map.put(num, map.getOrDefault(num, 0) 1); } PriorityQueueInteger pq new PriorityQueue(new ComparatorInteger() { public int compare(Integer a, Integer b) { return map.get(a) map.get(b) ? 1 : -1; } }); for (Integer key: map.keySet()) { if (pq.isEmpty() || pq.size() k) { pq.offer(key); continue; } if (map.get(pq.peek()) map.get(key)) { pq.poll(); pq.offer(key); } } int[] result new int[k]; int i 0; while(!pq.isEmpty()) { result[i] pq.poll(); } return result; } }