网站右侧出现百度名片叫什么,青岛模板化网站建设,好的建网站的书籍,seo优化排名是什么文章目录题目描述思路 代码更新版#xff1a;引入 stream 流 Lambda题目描述
时间复杂度小于O(n*logn)#xff0c;否则直接sort#xff0c;再遍历就很轻松。很有学习价值的题目#xff0c;第一次使用了优先队列PriorityQueue。
思路 代码
首先遍历数组 代码更新版引入 stream 流 Lambda题目描述
时间复杂度小于O(n*logn)否则直接sort再遍历就很轻松。很有学习价值的题目第一次使用了优先队列PriorityQueue。
思路 代码
首先遍历数组用HashMap存储 元素值 - 频率 映射然后维护一个容量为 k 的小顶堆重写比较器注意写法遍历哈希表存入小顶堆中接着把最终的小顶堆存入数组即可
class Solution {// TreeMap重写comparatorpublic int[] topKFrequent(int[] nums, int k) {// 先用HashMap存储 元素 - 频率 映射 O(n) O(n)MapInteger, Integer hashmap new HashMap();for(int i 0; i nums.length; i){if(hashmap.containsKey(nums[i])){hashmap.put(nums[i], hashmap.get(nums[i]) 1);}else{hashmap.put(nums[i], 1);}}// PriorityQueue, 维护一个容量为k的优先队列小顶堆PriorityQueueInteger pq new PriorityQueue(new ComparatorInteger(){// 设定以频率分高下Overridepublic int compare(Integer key1, Integer key2){return hashmap.get(key1) - hashmap.get(key2);}});// 遍历哈希表轮流对比存入优先队列中 O(n)for(Integer key : hashmap.keySet()){// 未满情况if(pq.size() k){pq.add(key);}// 满了情况对比替换else if(hashmap.get(key) hashmap.get(pq.peek())){// 移头新增pq.remove();pq.add(key);}}// 获取答案 O(n)int[] ans new int[k];for(int i 0; i k; i){ans[i] pq.remove();}return ans;}
}更新版引入 stream 流 Lambda
class Solution {public int[] topKFrequent(int[] nums, int k) {MapInteger, Integer map new HashMap();for(int temp : nums) {if(map.containsKey(temp)) {map.put(temp, map.get(temp) 1);}else {map.put(temp, 1);}}PriorityQueueInteger queue new PriorityQueue((Integer a, Integer b) - (map.get(a) - map.get(b)));for(Map.EntryInteger, Integer entry : map.entrySet()) {if(queue.size() k) {queue.add(entry.getKey());}else if(entry.getValue() map.get(queue.peek())) {queue.remove();queue.add(entry.getKey());}}return queue.stream().mapToInt(Integer::valueOf).toArray();}
}
