Medium
692. Top K Frequent Words
arrayhash-tablestringtriesortingheap-priority-queuebucket-sortcounting
解題說明
Top K Frequent Words
題目描述：給定一個字串陣列 words 和整數 k，回傳出現頻率最高的前 k 個單字。結果按頻率由高到低排列，頻率相同則按字典序排列。
解題思路：先用雜湊表統計每個單字的出現次數。然後使用大小為 k 的最小堆（min-heap）來維護前 k 個最高頻率的單字。自訂比較器：頻率低的優先（以便彈出），頻率相同時字典序大的優先（以便保留字典序小的）。最後從堆中逐一取出並反轉結果。
C++ 解法
複雜度分析
時間複雜度：O(n log k) — 統計頻率 O(n)，每個元素入堆 O(log k)，共 n 個不同元素。
空間複雜度：O(n) — 雜湊表存所有不同單字的頻率。
虛擬碼
1. Build frequency map: word -> count 2. Create min-heap of size k with custom comparator: - Lower frequency has higher priority (min-heap behavior) - Same frequency: lexicographically larger word has higher priority 3. For each (word, count) in frequency map: a. Push onto heap b. If heap size > k, pop the top (least frequent / lexicographically largest) 4. Pop all elements from heap into result array 5. Reverse result (heap gives ascending order, we need descending) 6. Return result
其他解法
桶排序 O(n)：建立頻率桶（bucket[i] = 所有出現 i 次的單字列表），從最大頻率桶開始收集，每個桶內按字典序排列。時間 O(n)（假設桶內排序的字串長度有界），避免了堆的 log k 因子。
排序法 O(n log n)：將 (count, word) 配對直接排序，取前 k 個。簡單但時間 O(n log n) 不如堆方法的 O(n log k)。
延伸思考
- 能否在 O(n) 時間內解決此問題？（提示：桶排序）
- 如果 k 很大（接近不同單字數量），堆方法是否仍然最優？
- 如何擴展此問題以支援串流資料（單字不斷到達）？