題幹與適用場景
給定單字陣列 words 和整數 k，返回出現頻率最高的 k 個單字；頻率相同的單字按字典序升序排列。
面試重點是如何維護大小為 k 的候選集合，以及堆頂應代表「最差候選」還是「最佳候選」。不要求綁定 Java；範例使用 Java 只為展示比較器。
面試官考察點
計數
候選人應先用雜湊表統計每個單字頻率，並說明唯一單字數 m 與陣列長度 n 的關係。
排序規則
頻率高者優先；頻率相同則字典序小者優先。最小堆應把較差的候選放在堆頂，方便超過 k 時淘汰。
複雜度
完整排序是 O(m log m)；大小為 k 的堆是 O(n + m log k)，適合 k 遠小於唯一單字數的情況。
正確性
要解釋堆比較器與最終輸出順序不同：堆用於淘汰，結果需要反轉或按最佳順序重新建立。
回答前需要釐清的問題
- 單字是否只包含小寫英文，是否區分大小寫？
k是否保證在 1 到唯一單字數之間？- 字典序按 ASCII、Unicode，還是業務 locale？
- 是否需要串流處理，不能把所有詞放入記憶體？
- 輸出是否必須穩定，是否允許任意順序？
- 頻率是否可能超過 32 位整數範圍？
30 秒回答框架
「我先用雜湊表統計頻率。對每個唯一單字維護大小為 k 的最小堆，堆頂定義為較差的候選：頻率更低，或頻率相同但字典序更大。每次加入後若超過 k 就彈出堆頂。最後把堆中單字按『頻率降序、字典序升序』取出。計數 O(n)，堆維護 O(m log k)，空間 O(m)。
分步驟深入解答
第一步：統計頻率
遍歷陣列，把每個詞映射到出現次數。若輸入來自串流日誌，可先在外部聚合或使用近似計數，但本題預設記憶體可容納唯一詞表。
第二步：定義最差候選
候選 A 比 B 更差，當 A 頻率更低；若頻率相同，A 的字典序更大。比較器讓最差候選位於堆頂。
第三步：維護大小 k
遍歷頻率表，將每個詞加入堆；堆大小超過 k 時彈出一個。這樣堆中始終保留目前最有可能進入答案的 k 個詞。
第四步：產生輸出
從堆中彈出的順序是從最差到較好，不能直接作為答案。把元素放入陣列後反向讀取，或使用最終排序器按頻率降序和字典序升序排列。
第五步：證明正確性
每次超過 k 時刪除目前集合中最差元素；因此被刪除的詞不可能優於堆中保留的 k 個詞。歸納到遍歷結束，堆包含全域 Top K。
第六步：處理邊界
檢查 k=1、所有詞頻相同、只有一個唯一詞、重複詞很多和 k=m。比較器必須避免頻率相同的詞順序反轉。
高品質示範回答
class Solution {
public List<String> topKFrequent(String[] words, int k) {
Map<String, Integer> count = new HashMap<>();
for (String word : words) count.merge(word, 1, Integer::sum);
PriorityQueue<String> heap = new PriorityQueue<>((a, b) -> {
int byFrequency = Integer.compare(count.get(a), count.get(b));
if (byFrequency != 0) return byFrequency;
return b.compareTo(a); // 字典序較大的較差，放在堆頂
});
for (String word : count.keySet()) {
heap.offer(word);
if (heap.size() > k) heap.poll();
}
List<String> answer = new ArrayList<>();
while (!heap.isEmpty()) answer.add(heap.poll());
Collections.reverse(answer);
return answer;
}
}計數需要 O(n)，唯一詞數為 m 時每次堆操作 O(log k)，總時間 O(n + m log k)，空間 O(m)。
常見錯誤
- 比較器把最佳候選放在堆頂 → 淘汰了正確答案 → 讓最差候選位於堆頂。
- 頻率相同時字典序方向寫反 → 輸出順序錯誤 → 頻率相同按字典序升序保留。
- 堆彈出結果直接返回 → 結果從差到好 → 反轉或用最終排序器重排。
- 先全量排序卻聲稱 O(n log k) → 複雜度不成立 → 全量排序為 O(m log m)。
- 只測試不同頻率 → 平局規則未驗證 → 測試所有詞頻相同和大量同頻詞。
- 忽略
k=m→ 不必要的淘汰或越界 → 允許堆增長到全部唯一詞。 - 使用不穩定的 locale 比較 → 跨環境結果變化 → 明確題目規定的字典序規則。
- 只說雜湊表不解釋空間 → 無法評估規模 → 給出 n、m、k 的複雜度。
追問及應對
追問一：k 接近唯一詞數時還用堆嗎？
當 k 接近 m，全量排序的常數和實作複雜度可能更合適；仍可使用堆，但要說明 O(m log k) 接近 O(m log m)。
追問二：輸入是無限串流怎麼辦？
頻率計數仍需狀態；可採用視窗、外部聚合或近似演算法。若要求精確 Top K，就必須保留足夠的計數狀態。
追問三：單字數量超過記憶體怎麼辦？
先分區雜湊到磁碟，分別統計後合併候選；也可用外部排序。不能直接把完整陣列塞進記憶體。
追問四：如何支援大小寫不敏感？
計數前按明確 locale 正規化，輸出保留原文還是正規化形式要先定義，並避免不同正規化形式重複計數。
追問五：如何測試比較器？
構造頻率相同、字典序相反、k=1、k=m 和重複資料的斷言；再與全量排序的基準實作做隨機對拍。
來源一：LeetCode 692
LeetCode 題目定義了頻率降序、同頻字典序升序和 O(n log k) 追問，明確了本題的輸出規則與複雜度目標。
來源二：NeetCode Top K
NeetCode 展示了頻率表與 Top K 維護的常見解法，並提醒比較器和堆/排序取捨是核心。
來源三：Oracle PriorityQueue
Oracle 文件說明 PriorityQueue 按自然順序或 Comparator 維護優先級，為自訂最小堆比較器和 poll 語義提供依據。