前 K 个高频元素

张开发
• 2026/4/17 8:47:15 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

前 K 个高频元素
要求给定一个非空的整数数组返回其中出现频率前 k 高的元素。示例 1:输入: nums [1,1,1,2,2,3], k 2输出: [1,2]示例 2:输入: nums [1], k 1输出: [1]提示你可以假设给定的 k 总是合理的且 1 ≤ k ≤ 数组中不相同的元素的个数。你的算法的时间复杂度必须优于O(nlog⁡n)O(n \log n)O(nlogn), n 是数组的大小。题目数据保证答案唯一换句话说数组中前 k 个高频元素的集合是唯一的。你可以按任意顺序返回答案。思路统计频率遍历数组 nums使用 HashMap 记录每个数字出现的次数。维护前 K 个高频元素使用一个 小顶堆PriorityQueue来存储数字。小顶堆的比较逻辑是频率越低优先级越高在堆顶。遍历 HashMap 的键值对。将数字加入堆中如果堆的大小超过了 k就弹出堆顶元素弹出的是当前堆中频率最低的那个。这样遍历完所有数字后堆中剩下的就是频率最高的 k 个元素。输出结果将堆中的 k 个元素依次取出放入结果数组。题解public int[] topKFrequent(int[] nums, int k){MapInteger,Integer map new HashMap();for (int num : nums) {map.put(num, map.getOrDefault(num, 0) 1);}PriorityQueueInteger queue new PriorityQueue((a, b) - map.get(a) - map.get(b)); for (Integer num : map.keySet()) { queue.add(num); if (queue.size() k) { queue.poll(); } } int[] res new int[k]; for (int i k - 1; i 0; i--) { res[i] queue.poll(); } return res;}注意new出PriorityQueue时要使用lambda表达式指明比较规则map.get(a) - map.get(b)是按照每个数字出现的频率降序比较确保堆顶始终是出现频率最小的数字。

更多文章