題目描述:給定一個字串陣列 words 和整數 k,回傳出現頻率最高的前 k 個單字。結果按頻率由高到低排列,頻率相同則按字典序排列。
解題思路:先用雜湊表統計每個單字的出現次數。然後使用大小為 k 的最小堆(min-heap)來維護前 k 個最高頻率的單字。自訂比較器:頻率低的優先(以便彈出),頻率相同時字典序大的優先(以便保留字典序小的)。最後從堆中逐一取出並反轉結果。
時間複雜度: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)。