題目
#

leetcode 347 - Top K Frequent Elements (題目說明請點連結)

題目簡述
#

給一個整數陣列 nums 和一個整數 k，請返回陣列中出現頻率最高的前 k 個元素。可以按任意順序返回答案。
注意：題目保證答案唯一，即前 k 個高頻元素的集合是唯一的。

範例
#

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Explanation: 
- 元素 1 出現 3 次
- 元素 2 出現 2 次  
- 元素 3 出現 1 次
- 前 2 個高頻元素是 [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]
Explanation: 
- 元素 1 出現 1 次
- 前 1 個高頻元素是 [1]

Example 3:

Input: nums = [1,1,1,2,2,3,3,3,3], k = 3
Output: [3,1,2]
Explanation: 
- 元素 3 出現 4 次
- 元素 1 出現 3 次
- 元素 2 出現 2 次
- 前 3 個高頻元素是 [3,1,2]

解題思路
#

這題要求我們找出陣列中出現頻率最高的前 k 個元素。我們可以使用HashMap來統計每個元素的出現次數，然後使用頻率陣列（Bucket Sort）的方法來快速找到前 k 個高頻元素。

解法
#

使用 HashMap 統計每個元素的出現次數
創建頻率陣列 freqList，索引代表頻率，值代表具有該頻率的元素列表
從高頻率開始遍歷，收集前 k 個高頻元素
返回結果陣列

步驟
#

統計頻率：
- 使用 HashMap 遍歷陣列，統計每個元素的出現次數
創建頻率陣列：
- 創建長度為 nums.length + 1 的陣列 freqList
- 對於每個元素，將其加入到對應頻率的列表中
收集高頻元素：
- 從高頻率開始遍歷 freqList
- 收集元素直到達到 k 個
返回結果：
- 將收集到的元素轉換為陣列並返回

例子說明
#

nums = [1, 1, 1, 2, 2, 3], k = 2

步驟	操作	HashMap	freqList	說明
初始化	-	{}	[null, null, null, null, null, null, null]	創建空的 HashMap 和頻率陣列
統計頻率	遍歷 1	{1: 1}	[null, [1], null, null, null, null, null]	元素 1 出現 1 次
統計頻率	遍歷 1	{1: 2}	[null, [1], [1], null, null, null, null]	元素 1 出現 2 次
統計頻率	遍歷 1	{1: 3}	[null, [1], [1], [1], null, null, null]	元素 1 出現 3 次
統計頻率	遍歷 2	{1: 3, 2: 1}	[null, [1, 2], [1], [1], null, null, null]	元素 2 出現 1 次
統計頻率	遍歷 2	{1: 3, 2: 2}	[null, [1, 2], [1, 2], [1], null, null, null]	元素 2 出現 2 次
統計頻率	遍歷 3	{1: 3, 2: 2, 3: 1}	[null, [1, 2, 3], [1, 2], [1], null, null, null]	元素 3 出現 1 次
收集高頻元素	從頻率 3 開始	-	-	頻率 3：收集 [1]
收集高頻元素	從頻率 2 開始	-	-	頻率 2：收集 [1, 2]，已達 k=2 個

最終結果： [1, 2]

頻率統計說明：

頻率 1：元素 [1, 2, 3]（各出現 1 次）
頻率 2：元素 [1, 2]（各出現 2 次）
頻率 3：元素 [1]（出現 3 次）

前 k 個高頻元素：

元素 1：出現 3 次（最高頻率）
元素 2：出現 2 次（第二高頻率）

完整程式碼
#

java

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 使用 HashMap 統計每個元素的出現次數
        Map<Integer, Integer> map = new HashMap<>();
        
        // 遍歷陣列，統計頻率
        for(int n : nums){
            map.put(n, map.getOrDefault(n, 0) + 1);
        }

        // 創建頻率陣列，索引代表頻率，值代表具有該頻率的元素列表
        List<Integer>[] freqList = new List[nums.length + 1];

        // 將每個元素加入到對應頻率的列表中
        for(int key : map.keySet()){
            int freq = map.get(key);
            if(freqList[freq] == null){
                freqList[freq] = new ArrayList<>();
            }
            freqList[freq].add(key);
        }

        // 收集前 k 個高頻元素
        List<Integer> res = new ArrayList<>();

        // 從高頻率開始遍歷，直到收集到 k 個元素
        for(int i = freqList.length - 1; i >= 0 && res.size() < k; i--){
            if(freqList[i] != null){
                res.addAll(freqList[i]);
            }
        }

        // 將結果轉換為陣列
        int[] ans = new int[k];
        for(int i = 0; i < k; i++){
            ans[i] = res.get(i);
        }

        // 返回結果陣列
        return ans;
    }
}