题干与适用场景
给定单词数组 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 语义提供依据。