题目描述
给定一个非空的整数数组,返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
提示:
- 你可以假设给定的 k 总是合理的,且 1 ≤ k ≤ 数组中不相同的元素的个数。
- 你的算法的时间复杂度必须优于$O(nlogn)$ , n 是数组的大小。
- 题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的。
- 你可以按任意顺序返回答案。
解法
1. 堆
思路:使用HashMap储存每个数字出现的频次,然后进行排序,得到前k个高频元素。但这样时间复杂度会超过或等于$O(nlogn)$。可以维护一个大小为k的堆,将数字加入堆中,当有数字的频次高于堆顶数字的频次,就删除堆顶数字,将该数字入堆。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| import java.util.HashMap; import java.util.PriorityQueue;
class Solution { public int[] topKFrequent(int[] nums, int k) { if (nums == null || nums.length == 0) return new int[0]; HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if (map.containsKey(nums[i])) { map.put(nums[i], map.get(nums[i]) + 1); } else { map.put(nums[i], 1); } } PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() { @Override public int compare(int[] m, int[] n) { return m[1] - n[1]; } }); for (Integer num: map.keySet()) { int n = num, count = map.get(num); if (pq.size() == k) { if (pq.peek()[1] < count) { pq.poll(); pq.offer(new int[]{n, count}); } } else { pq.offer(new int[]{n, count}); } } int[] res = new int[k]; for (int i = 0; i < k; i++) { res[i] = pq.poll()[0]; } return res; } }
|
时间复杂度为$O(nlogk)$ 统计频次的时间复杂度为$n$,维护堆的时间复杂度为$logk$
空间复杂度为$O(n)$ 哈希表$O(n)$ 堆$O(k)$
参考