【大根堆 Java】使用優先隊列+HashMap 解決前 K 個高頻元素問題

一、題目描述

給你一個整數數組 nums 和一個整數 k ，請你傳回其中出現頻率前 k 高的元素。你可以按 任意順序 傳回答案。

示例

二、思路

本題我們主要完成兩個步驟：

1. 統計出每個元素出現的次數
2. 找出出現次數最多的前 K 個元素

• 對第一個步驟，我們可以使用 HashMap 進行統計，統計方法如下：

這一步中，最需要學習的就是

getOrDefault()

的使用，其若是在 map 中找對對應 key 的 value，則傳回 value 值，否則傳回我們設定的預設值

Map<Integer, Integer> map = new HashMap<>();
        for(int i=0; i<nums.length; i++){
            map.put(nums[i], map.getOrDefault(nums[i], 0));
        }
           

• 對第二個步驟 ——

  1.首先我們建立一大根堆，建立方式為使用 Java 語言為我們提高的優先隊列 PriorityQueue

  2.然後我們将上面步驟得到的 HashMap 中的每個映射存放到這個優先隊列中

  3.從優先隊列中取出前 K 個元素

擴充知識：

優先隊列中存儲的類型為 Map.Entry<Integer, Integer> ， —— 這個 Map.Entry 是什麼？

答： Map中存放的元素均為鍵值對，每一個鍵值對必然存在一個映射關系 ，Map中采用Entry内部類來表示一個映射項，映射項包含Key和Value

也就是說 每一個鍵值對就是一個Entry，Map.Entry裡面包含getKey()和getValue()方法

第二步代碼：

Set<Map.Entry<Integer, Integer>> entries = map.entrySet(); // 用于周遊向大根堆中加入鍵值對
      // 根據map中的value值，建構于一個大頂堆（o1 - o2: 小根堆， o2 - o1 : 大根堆）
      PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((o1, o2) -> o2.getValue() - o1.getValue());
      for (Map.Entry<Integer, Integer> entry : entries) { // 将鍵值對加入大根堆中
          queue.offer(entry);
      }
      for (int i = k - 1; i >= 0; i--) { // 取出前K個元素
          result[i] = queue.poll().getKey();
      }
           

三、完整代碼

public int[] topKFrequen2(int[] nums, int k) {
        int[] res = new int[k];

        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0; i<nums.length; i++){
            map.put(nums[i], map.getOrDefault(nums[i], 0));
        }
        
        Set<Map.Entry<Integer, Integer>> set = map.entrySet();
        PriorityQueue<Map.Entry<Integer, Integer>> priorityQueue = new PriorityQueue<>((o1, o2) -> (o2.getValue() - o1.getValue()));
        for(Map.Entry<Integer, Integer> entry: set){
            priorityQueue.add(entry);
        }
        
        for(int i=0; i<=k; i++){
            res[i] = priorityQueue.poll().getKey();
        }
        
        return res;
    }