LeetCode - Top K Frequent Elements（出現頻率最高的 K 個元素）

題目描述

給定一個非空的整數數組 nums，返回其中出現頻率最高的前 k 個元素。

範例：

輸入：nums = [1,1,1,2,2,3], k = 2
輸出：[1,2]

輸入：nums = [1], k = 1
輸出：[1]

解法思路

要找到頻率最高的 k 個元素，最有效的方法是利用 哈希表 記錄每個數字的出現次數，然後將這些數據進行排序或用結構來提取出前 k 個頻率最高的元素。

方法一：哈希表 + 最小堆

1. 計算頻率：使用哈希表（字典）來統計每個元素的出現次數。
2. 使用最小堆：將字典中的每個元素按照頻率推入最小堆中，維護堆的大小為 k。
   • 當堆的大小超過 k 時，彈出最小頻率的元素。
3. 提取結果：最小堆中剩下的 k 個元素即為出現頻率最高的前 k 個元素。

方法二：桶排序

1. 計算頻率：同樣使用哈希表來統計每個元素的頻率。
2. 桶排序：使用桶排序，將頻率 i 的所有元素放到一個桶 buckets[i] 中，桶索引表示頻率。
3. 提取結果：從高頻到低頻遍歷桶，收集元素直到獲得 k 個元素。

範例代碼

以下是使用 最小堆 的 Python 實現：

import heapq
from collections import Counter

def topKFrequent(nums, k):
    # 使用 Counter 計算每個元素的頻率
    count = Counter(nums)
    
    # 使用最小堆存放頻率最高的 k 個元素
    heap = []
    for num, freq in count.items():
        heapq.heappush(heap, (freq, num))  # 頻率放在前面，方便比較
        if len(heap) > k:
            heapq.heappop(heap)  # 當堆的大小超過 k，彈出最小頻率的元素
    
    # 提取堆中的元素，即為出現頻率最高的 k 個元素
    return [num for freq, num in heap]

代碼解析

1. 統計頻率：使用 Counter 對 nums 中每個元素計數。
2. 維護最小堆：將每個元素和其頻率加入最小堆，並在堆大小超過 k 時，彈出頻率最低的元素。
3. 返回結果：最終堆中的元素即為出現頻率最高的 k 個元素。

時間和空間複雜度

• 時間複雜度：O(n log k)，其中 n 是數組長度，log k 是由於維護最小堆的大小。
• 空間複雜度：O(n)，用於存儲哈希表和最小堆。