原文題目

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

題目摘要

1. 問題描述：給定一個整數陣列 nums 和一個整數 k，要求返回出現頻率最高的 k 個元素。
2. 輸入：nums：一個包含 n 個整數的陣列、k：要求返回的頻率最高的元素個數。
3. 輸出：回傳一個包含 k 個整數的陣列。

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

解題思路

1. 計算頻率：
   • 首先，建立一個 HashMap（frequencyMap）來儲存每個元素的頻率。
2. 使用minHeap找出頻率前 k 高的元素：
   • 使用 PriorityQueue（minHeap）實現minHeap。minHeap的大小維持為 k，這樣可以確保Heap中始終包含頻率最高的 k 個元素。
   • 遍歷 frequencyMap 中的每一個 Map.Entry（頻率-數字對），將它們加入最小堆。
   • 當最小堆的大小超過 k 時，移除堆頂元素（頻率最小的元素）。
3. 提取結果並回傳：
   • 從minHeap中提取所有元素，並將提取出的元素添加到 result 列表中。

程式碼

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> frequencyMap = new HashMap<>(); //設立一個HashMap來計算每個元素的頻率
        //遍歷整個陣列
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1); //更新每個元素的頻率
        }
        
        //使用最小堆來維護頻率最高的k個元素，頻率較低的元素會被移除
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(
            (n1, n2) -> frequencyMap.get(n1) - frequencyMap.get(n2)
        );
        
        //
        for (int num : frequencyMap.keySet()) {
            minHeap.add(num); //將每個元素加入最小堆
            //如果堆的大小超過k，移除最小的元素
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        
        int[] result = new int[k]; //設立一個結果陣列來儲存頻率最高的k個元素
        //堆中存儲的是頻率最高的k個元素，將最小堆中的元素放入結果陣列中
        for (int i = 0; i < k; i++) {
            result[i] = minHeap.poll();
        }
        return result; //回傳結果陣列        
    }
}

結論： 在寫這題時，完全沒有思緒如何去寫出一個minHeap，甚至還要能使其一直維持著minHeap該有的規則。就這樣腦袋空空的去參考了LeetCode上許多人分享的解題影片、文章，甚至直接研讀程式碼，才第一次跳出了課本上教的排序知識，第一次接觸到這樣的排序是該如何透過程式碼去實現。覺得是非常有趣的！過去學習的各種排序演算法，只是在書上學習了和Day13那天文章的理論知識，從沒想過要如何用程式碼實現，是很新奇又興奮的一次機會！