上海南山做网站,小企业一键做网站,湖南省住房和城乡建设厅网站,网站开发师是做什么的使用最小堆算法来解决这道题目#xff1a;相当于有一个容量固定为K的教室#xff0c;只能容纳 K 个人#xff0c;学生们逐个逐个进入该教室#xff0c;当教室容量达到K人之后#xff0c;每次进入一个新的学生后#xff0c;我们将分数最低的学生(类似本题中的频率最低元素…
使用最小堆算法来解决这道题目相当于有一个容量固定为K的教室只能容纳 K 个人学生们逐个逐个进入该教室当教室容量达到K人之后每次进入一个新的学生后我们将分数最低的学生(类似本题中的频率最低元素)赶出去最后所有学生都遍历结束之后教室里所余的学生就是成绩前K高的学生们。
在这道题目中最小堆PriorityQueue就像是一个只能容纳 K 个学生的教室每次加入一个新的学生教室满了就会将成绩最低的学生即频率最低的元素移除出去。最终剩下的 K 个学生就是成绩最高的 K 个学生。
具体步骤如下
我们先统计每个元素的出现频率类似学生的分数。然后我们使用一个容量为 K 的最小堆来维护当前频率最高的 K 个元素。 当堆的大小超过K时将频率最低的元素移除这样堆中始终只会保留频率最高的K个元素。 最后堆中剩下的元素就是前K个高频元素。
这个方法的复杂度主要取决于建立和维护堆的过程大概是O(N log K) 的时间复杂度其中N是数组的长度K是要返回的高频元素的个数。
class Solution {public int[] topKFrequent(int[] nums, int k) {//首先利用 Hashmap 统计每个数值的频率MapInteger, Integer freqMap new HashMap();for(int num : nums) {freqMap.put(num, freqMap.getOrDefault(num, 0) 1);}//创建最小堆,存储键值对对象,key 代表元素,value 代表对应的频率值. // 比较器 (a, b) - a.getValue() - b.getValue() 隐式地比较了两个元素的频率 // 如果 a 的值(频率)小于 b则 a 会排在 b 前面因为最小堆会将频率最小的元素放在堆顶PriorityQueueMap.EntryInteger, Integer minHeap new PriorityQueue(k, (a, b) - a.getValue() - b.getValue()); //维护一个大小为 k 的最小堆for(Map.EntryInteger, Integer entry : freqMap.entrySet()) {// 遍历插入一个新的键值对而不是元素;键是唯一的没有重复//由于堆顶元素始终是最小的元素,所以无论当前offer提供的待插入元素的大小与此时堆顶元素的大小如何都会被插入堆中并自动调整。minHeap.offer(entry);if(minHeap.size() k) { minHeap.poll(); }}int[] results new int[k];for(int i 0; i k; i) {results[i] minHeap.poll().getKey();}return results;}
}
