阅读量:7
2024 7/14
1、题目描述
2、算法分析
我的初步想法就是：创建一个哈希映射表，将键值对存储进去，那么我们怎么将出现频率前k高的元素给取出来呢？这就有点犯难了，那也只能看看题解啦！题解说利用堆排序，就可以将哈希表里面的进行排序，之后直接取出前k个值即可。
思路：
- 统计频率：
使用哈希表（HashMap）来统计每个数字在输入数组中出现的频率。这是因为哈希表提供了快速的键值对查找、插入和更新操作，非常适合用于计数任务。 - 利用优先队列（最大堆）：
创建一个优先队列（PriorityQueue），并通过自定义比较器将其配置为最大堆。最大堆是一种特殊的完全二叉树，其中每个父节点的值都大于或等于其子节点的值。在Java中，PriorityQueue默认是小顶堆，但可以通过提供自定义比较器来实现大顶堆。将哈希表中每个条目（即数字及其频率）作为Map.Entry对象添加到优先队列中。由于队列是按照频率降序排列的，因此频率最高的元素将始终位于队列的顶部。使用Lambda表达式可以实现大根堆排序：(a, b) -> b.getValue() - a.getValue()) - 维护前k个高频元素：
由于只需要找到前k个高频元素，因此可以限制优先队列的大小为k。当尝试添加一个新元素到队列中，并且队列的大小已经达到k时，队列会自动移除当前频率最低的元素（即队列的底部元素），以保持队列中只有频率最高的k个元素。 - 提取结果：
最后，遍历优先队列（实际上是从队列中依次移除元素，因为poll()方法会移除并返回队列的头部元素），将前k个高频元素的键（即数字）存储在结果数组中并返回。
3、代码
public int[] topKFrequent(int[] nums, int k) { // 创建一个HashMap来统计每个数字出现的频率 Map<Integer, Integer> map = new HashMap<Integer, Integer>(); // 遍历输入的整数数组nums for(int num : nums){ // 使用getOrDefault方法更新每个数字的频率，如果不存在则默认为0 map.put(num, map.getOrDefault(num, 0) + 1); } // 创建一个PriorityQueue（优先队列，这里用作最大堆），按照Map.Entry的value（即频率）降序排列 PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>( // 使用lambda表达式定义比较器，确保队列按照频率降序排列 (a, b) -> b.getValue() - a.getValue()); // 将HashMap中的所有条目（即数字及其频率）添加到优先队列中 for(Map.Entry<Integer, Integer>entry : map.entrySet()){ queue.offer(entry); } // 创建一个大小为k的整数数组来存储结果 int[] res = new int[k]; // 从优先队列中依次取出前k个频率最高的数字（即堆顶元素） for(int i = 0; i < k; i++){ // poll方法会移除并返回队列的头部元素（这里是最大元素） res[i] = queue.poll().getKey(); } // 返回包含前k个最高频率数字的结果数组 return res; } 4、示例演示
初始数组为[1,1,1,2,2,3]
初始化HashMap并统计频率。
初始化最大堆优先队列，并将HashMap中的条目添加到队列中。
从队列中依次移除并返回前k个元素（在这个例子中是前两个元素），将它们的键存储在结果数组中。
返回结果数组[1, 2]。
5、复杂度分析
- 时间复杂度：
O(Nlogk)，其中 N 为数组的长度。我们首先遍历原数组，并使用哈希表记录出现次数，每个元素需要 O(1) 的时间，共需O(N) 的时间。随后，我们遍历「出现次数数组」，由于堆的大小至多为 k，因此每次堆操作需要 O(logk) 的时间，共需O(Nlogk) 的时间。二者之和为 O(Nlogk)。 - 空间复杂度：
O(N)。哈希表的大小为 O(N)，而堆的大小为 O(k)，共计为 O(N)。
okok，那就先这样吧，我的外卖到啦，吃饭去咯！
