文章目錄

• 題目描述
• 思路 & 代碼
• • • 更新版：引入 stream 流 + Lambda

題目描述

• 時間復雜度小于O(n*logn)，否則直接sort，再遍歷就很輕松。
• 很有學習價值的題目，第一次使用了優先隊列PriorityQueue。
  

思路 & 代碼

• 首先遍歷數組，用HashMap存儲 元素值 - 頻率 映射
• 然后維護一個容量為 k 的小頂堆（重寫比較器，注意寫法），遍歷哈希表存入小頂堆中
• 接著把最終的小頂堆存入數組即可

class Solution {// TreeMap重寫comparator？public int[] topKFrequent(int[] nums, int k) {// 先用HashMap存儲 元素 - 頻率 映射 O(n) O(n)Map<Integer, 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的優先隊列：小頂堆PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){// 設定以頻率分高下@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) {Map<Integer, Integer> map = new HashMap<>();for(int temp : nums) {if(map.containsKey(temp)) {map.put(temp, map.get(temp) + 1);}else {map.put(temp, 1);}}PriorityQueue<Integer> queue = new PriorityQueue<>((Integer a, Integer b) -> (map.get(a) - map.get(b)));for(Map.Entry<Integer, 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();} }

總結

以上是生活随笔為你收集整理的【LeetCode笔记】347. 前K个高频元素（Java、优先队列、小顶堆、HashMap）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。