LeetCode 692. 前K个高频单词——稳定排序与Comparator设计
LeetCode 692. 前K个高频单词——稳定排序与Comparator设计
适读人群：Java 中级工程师、备战面试的同学 | 阅读时长：约20分钟 | 难度：中等
开篇故事
这道题是 347「前K高频元素」的字符串版，但有一个关键的额外约束：频率相同时，字典序更小的单词排在前面。
这个约束不起眼，却直接决定了 Comparator 的设计方式，也是这道题最容易踩坑的地方。
我在代码评审里见过好多种写法，有些看起来能跑但实际上不满足稳定性要求，有些 Comparator 写错了方向，让字典序大的反而排在前面。今天把 Comparator 的设计方法讲清楚，这是 Java 工程中非常实用的技能。
一、题目解析
题目描述：
给定一个单词列表 words 和一个整数 k，返回前 k 个出现次数最多的单词。
返回的答案按单词出现频率由高到低排序。如果不同的单词有相同出现频率，则按字母顺序排序。
示例：
输入：words = ["i","love","leetcode","i","love","coding"], k = 2
输出：["i","love"]
输入：words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4
输出：["the","is","sunny","day"]二、解法一：排序 + 截取
思路分析
统计频率 → 排序（频率降序，相同频率按字典序升序）→ 取前K个。
Comparator 设计：
- 主排序键：频率降序（频率高的在前）
- 次排序键：字典序升序（字典序小的在前）
import java.util.*;
class Solution {
public List<String> topKFrequent(String[] words, int k) {
// 统计频率
Map<String, Integer> freqMap = new HashMap<>();
for (String word : words) {
freqMap.merge(word, 1, Integer::sum);
}
// 获取所有单词并排序
List<String> candidates = new ArrayList<>(freqMap.keySet());
candidates.sort((a, b) -> {
int freqDiff = freqMap.get(b) - freqMap.get(a); // 频率降序
if (freqDiff != 0) return freqDiff;
return a.compareTo(b); // 字典序升序
});
return candidates.subList(0, k);
}
}复杂度分析
- 时间复杂度：O(n log n)。统计 O(n)，排序 O(m log m)。
- 空间复杂度：O(n)。
三、解法二：最小堆（Comparator 反向设计）
思路分析
最小堆维护前K个高频单词。注意：堆是最小堆，堆顶是「最不应该保留的那个」，所以 Comparator 方向要反向：
- 频率低的排前面（堆顶），这样频率低的会被弹出
- 相同频率时，字典序大的排前面（堆顶），这样字典序大的会被弹出
import java.util.*;
class Solution {
public List<String> topKFrequent(String[] words, int k) {
Map<String, Integer> freqMap = new HashMap<>();
for (String word : words) {
freqMap.merge(word, 1, Integer::sum);
}
// 最小堆：堆顶是「最该被淘汰的」
// 频率小的 → 频率相同时字典序大的 → 应被淘汰
PriorityQueue<String> minHeap = new PriorityQueue<>((a, b) -> {
int freqDiff = freqMap.get(a) - freqMap.get(b); // 频率升序（小的在堆顶）
if (freqDiff != 0) return freqDiff;
return b.compareTo(a); // 字典序降序（大的在堆顶，先被弹出）
});
for (String word : freqMap.keySet()) {
minHeap.offer(word);
if (minHeap.size() > k) {
minHeap.poll(); // 弹出最不应保留的
}
}
// 收集结果，注意堆的输出顺序是最小堆顺序，需要反转
List<String> result = new ArrayList<>();
while (!minHeap.isEmpty()) {
result.add(minHeap.poll());
}
Collections.reverse(result); // 反转：让高频的在前
return result;
}
}复杂度分析
- 时间复杂度：O(n log k)。
- 空间复杂度：O(n)。
四、解法三（最优）：TreeMap 自动维护有序
核心思想
用 TreeMap 的自动排序特性，以自定义排序规则将单词存入 TreeMap，然后取前K个。
但更地道的做法是利用有序集合配合 Comparator，让 Java 标准库做重活：
完整代码（使用 TreeSet）
import java.util.*;
class Solution {
public List<String> topKFrequent(String[] words, int k) {
// 统计频率
Map<String, Integer> freqMap = new HashMap<>();
for (String word : words) {
freqMap.merge(word, 1, Integer::sum);
}
// TreeSet 自动按 Comparator 排序
// 注意：TreeSet 的 Comparator 返回0时认为是同一个元素（会覆盖/忽略）
// 所以当频率相同时，不能返回0，要用字典序区分
TreeSet<String> treeSet = new TreeSet<>((a, b) -> {
int freqDiff = freqMap.get(b) - freqMap.get(a); // 频率降序
if (freqDiff != 0) return freqDiff;
return a.compareTo(b); // 字典序升序（相同时用来区分，不返回0）
});
treeSet.addAll(freqMap.keySet());
List<String> result = new ArrayList<>();
Iterator<String> it = treeSet.iterator();
for (int i = 0; i < k; i++) {
result.add(it.next());
}
return result;
}
}Comparator 设计的关键细节
这道题的 Comparator 是整个解题的核心，让我详细解析：
目标排序规则： 频率高的在前，频率相同时字典序小的在前。
// 在排序（最终结果的顺序）中
(a, b) -> {
int freqDiff = freqMap.get(b) - freqMap.get(a); // b频率 - a频率 > 0 → a在b前 → 降序
if (freqDiff != 0) return freqDiff;
return a.compareTo(b); // a字典序 - b字典序 < 0 → a在b前 → 升序
}
// 在最小堆（堆顶是要被淘汰的）中，Comparator要反向
(a, b) -> {
int freqDiff = freqMap.get(a) - freqMap.get(b); // 频率低的排前（堆顶优先被淘汰）
if (freqDiff != 0) return freqDiff;
return b.compareTo(a); // 字典序大的排前（堆顶优先被淘汰）
}复杂度分析
- 时间复杂度：O(n log k)（使用 TreeSet 并限制大小） 或 O(n log n)（TreeSet 存所有元素）。
- 空间复杂度：O(n)。
五、举一反三
Comparator 的多键排序模式：
// 通用多键比较器
Comparator<T> multiKeyComparator = Comparator
.comparingInt((T t) -> primaryKey(t)).reversed() // 主键降序
.thenComparing(t -> secondaryKey(t)); // 次键升序本题用 Java 8 Comparator 链式写法：
Comparator.comparingInt((String w) -> freqMap.get(w))
.reversed()
.thenComparing(Comparator.naturalOrder())六、踩坑实录
坑一：最小堆 Comparator 方向搞反
排序用的 Comparator 和最小堆用的 Comparator 方向相反，这是最经典的错误。
- 排序：返回正数 → a 排在 b 后面（b 在前）
- 最小堆：返回正数 → a 被认为「更大」，排在堆的下层（不在堆顶）
在最小堆里，堆顶是「最小的」（最先被 poll 出来的）。我们想保留频率高的，所以把频率低的放堆顶（Comparator 中频率低的 a 返回负数，使 a 「更小」，排堆顶）。
坑二：TreeSet 的 Comparator 返回 0 会丢失元素
TreeSet 依赖 Comparator 来判断两个元素是否相同（不用 equals）。如果 Comparator 对不同的单词返回 0，TreeSet 会认为它们是同一个元素，只保留一个。
所以一定要在 Comparator 里保证不同的单词不会返回 0。字典序比较是天然的区分手段（相同字符串才返回 0，而不同单词字典序比较不会相等）。
坑三：subList 返回的是视图，不是独立 List
return candidates.subList(0, k); // 这是视图，原 list 修改会影响它
// 如果需要独立 list：
return new ArrayList<>(candidates.subList(0, k));七、总结
692 比 347 多了「同频率时字典序升序」的约束，这个约束对 Comparator 设计提出了更高要求。
掌握三种解法中 Comparator 的设计逻辑：
- 排序用：主键降序 + 次键升序
- 最小堆用：主键升序 + 次键降序（与排序相反）
- TreeSet 用：确保相等时也有区分（永远不返回 0）