LeetCode 937. 重新排列日志文件
目录
题目描述
题意分析
每条日志是一个字符串，由标识符、一个空格、以及内容组成。内容里可能还有更多空格，但第一个空格永远是标识符与内容的分界。按内容的第一个字符是字母还是数字，日志分成两类：字母日志与数字日志。
排序规则有三条，必须分别落到实现上：字母日志整体排在数字日志前面；字母日志之间先按内容的字典序排，内容完全相同时再按标识符的字典序排；数字日志之间保持输入的原相对顺序。
「保持原相对顺序」这句话就是稳定性要求。它意味着数字日志根本不该参与排序——只要按原顺序收集起来即可，比写一个「返回相等」的比较器更直接、也不依赖排序算法是否稳定。
「第一个空格是分界」这一点决定了切分方式：必须用「第一个空格」而不是把整串按空格切开取第 0 段和第 1 段。内容
"own kit dig"里有两个空格，按全部空格切分再拼回去既麻烦又容易丢信息。判断日志类型只需要看内容的第一个字符，也就是第一个空格后面那个字符——不是整条日志的首字符（那是标识符的首字符，标识符总是以字母开头），也不是最后一个字符。题目保证每条日志至少有一个空格且内容非空，所以这个字符一定存在。
约束里日志数量最多 100、每条长度最多 500，规模很小；这题考的是规则的翻译精度，不是效率。
边界：全是数字日志时原样返回；全是字母日志时按规则整体排序；两条字母日志内容相同、标识符不同时，由第二关键字决定先后。
解法：分桶 + 排序（字母日志）+ 稳定拼接
核心思路
一种常见写法是给整个数组写一个「大一统」比较器：两条都是字母日志就按内容再按标识符比；一条字母一条数字就让字母在前；两条数字就返回 0 表示相等。这个思路能通，但它把「数字日志保持原序」的正确性寄托在排序算法是否稳定上——Java 的
Arrays.sort(Object[])恰好稳定，而 Go 的sort.Slice并不稳定，同一套逻辑换个语言就会挂。瓶颈在于我们把「不需要排序的部分」也塞进了排序里。既然数字日志的目标顺序就是输入顺序，那就干脆不让它们参与排序。
于是策略变成三步：分桶 → 只排字母桶 → 按序拼接。遍历一遍把日志分进
letters与digits两个列表，分桶时按原顺序追加，digits的相对顺序天然保持；然后只对letters排序；最后先输出letters再输出digits。不变量：分桶结束时，
letters与digits各自内部保持输入的相对顺序，且两者的并集恰好是全部日志、无重复无遗漏。排序只改变letters内部的顺序，digits自始至终未被触碰。这样做的好处是规则与实现一一对应：第一条规则（字母在前）由拼接顺序保证，第二条（双关键字）由比较器保证，第三条（数字保序）由「不排序」保证。三条规则各归各位，任何一条改动都只影响一处代码，也不再依赖排序算法的稳定性这种隐含假设。
比较器本身是标准的双关键字写法：先切出标识符与内容，比较内容；内容相同再比较标识符。注意比较的是内容而不是整条日志——整条日志以标识符开头，直接比较会让标识符成为第一关键字，规则彻底反过来。
解题步骤
- 遍历
logs分桶：对每条日志用indexOf(' ')找到第一个空格的位置idx，取log.charAt(idx + 1)作为内容首字符。是数字就加入digits，否则加入letters。用「第一个空格」而不是最后一个或全部切分，是因为内容里可能还有空格。- 分桶时按遍历顺序追加：这一步就完成了「数字日志保持原相对顺序」，后面不再需要任何额外处理。
- 只对
letters排序，比较器双关键字：先各自substring(0, idx)取标识符、substring(idx + 1)取内容；先content比较，不为 0 直接返回；为 0 再比较标识符。第一关键字必须是内容——这是规则明确规定的，也是最容易写反的一处。- 不对
digits做任何排序：哪怕写一个「恒返回 0」的比较器也不推荐，因为它把正确性押在了排序稳定性上，换语言就失效。- 拼接结果，先
letters后digits：新建一个长度为logs.length的数组，按顺序填入。长度用原数组长度而不是两个桶长度之和，能顺带校验分桶没有丢失元素。- 返回结果数组。
以
logs = ["dig1 8 1 5 1", "let1 art can", "dig2 3 6", "let2 own kit dig", "let3 art zero"]走一遍。分桶阶段：
"dig1 8 1 5 1"：第一个空格在下标 4，内容首字符是'8'，是数字，进digits。
"let1 art can"：第一个空格在下标 4，内容首字符是'a'，是字母，进letters。
"dig2 3 6"：内容首字符'3'，进digits。
"let2 own kit dig"：内容首字符'o'，进letters。注意这条日志的内容"own kit dig"里还有两个空格，如果按全部空格切分只取第二段，内容会变成"own"，排序结果就错了。
"let3 art zero"：内容首字符'a'，进letters。分桶结果：
letters = ["let1 art can", "let2 own kit dig", "let3 art zero"]，digits = ["dig1 8 1 5 1", "dig2 3 6"]。排序阶段：三条字母日志的内容分别是
"art can"、"own kit dig"、"art zero"。按字典序，"art can"与"art zero"前四个字符相同（a、r、t、空格），第五位'c'小于'z'，所以"art can"在前；"own kit dig"首字符'o'大于'a'，排最后。三者内容互不相同，第二关键字（标识符）没有被用到。排序后letters = ["let1 art can", "let3 art zero", "let2 own kit dig"]。拼接阶段：先放三条字母日志，再放两条未经排序的数字日志，得到
["let1 art can", "let3 art zero", "let2 own kit dig", "dig1 8 1 5 1", "dig2 3 6"]。注意dig1仍在dig2之前，与输入顺序一致——虽然按字典序"3 6"小于"8 1 5 1"，但数字日志不排序。再看第二关键字什么时候起作用：若把输入换成
["g1 act car", "a8 act zoo", "a1 act car"]，三条都是字母日志，"g1 act car"与"a1 act car"内容完全相同，此时比较标识符，"a1"小于"g1"，所以a1排在g1前；"act zoo"的内容大于"act car"，a8排最后。结果是["a1 act car", "g1 act car", "a8 act zoo"]。如果误把整条日志当作排序键，"a1 act car"<"a8 act zoo"<"g1 act car"，顺序完全不同，直接答错。
代码实现
class Solution {
public String[] reorderLogFiles(String[] logs) {
List<String> letters = new ArrayList<>();
List<String> digits = new ArrayList<>();
for (String log : logs) {
int idx = log.indexOf(' ');
char first = log.charAt(idx + 1);
if (Character.isDigit(first)) {
digits.add(log);
} else {
letters.add(log);
}
}
letters.sort((a, b) -> {
int ia = a.indexOf(' ');
int ib = b.indexOf(' ');
String ida = a.substring(0, ia);
String idb = b.substring(0, ib);
String ca = a.substring(ia + 1);
String cb = b.substring(ib + 1);
int cmp = ca.compareTo(cb);
if (cmp != 0) {
return cmp;
}
return ida.compareTo(idb);
});
String[] answer = new String[logs.length];
int p = 0;
for (String s : letters) {
answer[p++] = s;
}
for (String s : digits) {
answer[p++] = s;
}
return answer;
}
}
func reorderLogFiles(logs []string) []string {
letters := make([]string, 0, len(logs))
digits := make([]string, 0, len(logs))
for _, log := range logs {
i := 0
for i < len(log) && log[i] != ' ' {
i++
}
if i+1 < len(log) && log[i+1] >= '0' && log[i+1] <= '9' {
digits = append(digits, log)
} else {
letters = append(letters, log)
}
}
sort.Slice(letters, func(i, j int) bool {
a := letters[i]
b := letters[j]
ia := indexSpace(a)
ib := indexSpace(b)
idA, idB := a[:ia], b[:ib]
contentA, contentB := a[ia+1:], b[ib+1:]
if contentA != contentB {
return contentA < contentB
}
return idA < idB
})
answer := make([]string, 0, len(logs))
answer = append(answer, letters...)
answer = append(answer, digits...)
return answer
}
func indexSpace(s string) int {
for i := 0; i < len(s); i++ {
if s[i] == ' ' {
return i
}
}
return -1
}
复杂度分析
- 时间复杂度：$O(nL \log n)$，其中 $n$ 是日志条数、$L$ 是单条日志的最大长度。分桶是 $O(nL)$；排序做 $O(n \log n)$ 次比较，每次比较要切分子串并逐字符比较，代价 $O(L)$，这一项占主导。
- 空间复杂度：$O(nL)$。两个桶合计存下全部日志的引用，比较器里每次
substring会产生新字符串（Java 7 之后substring会复制字符），排序过程中的临时对象也属同阶；结果数组本身也是 $O(n)$ 个引用。
关键点总结
- 排序题的第一步是把自然语言规则逐条翻译成实现位置：谁在前由拼接顺序决定，组内次序由比较器决定，保持原序由不参与排序决定。三条各归各位，改一条不会牵动其他两条。
- 「保持原相对顺序」不要依赖排序算法的稳定性。Java 的对象排序稳定而 Go 的
sort.Slice不稳定，同一套「返回 0」的写法换语言就会失效；把这部分数据排除在排序之外才是可移植的做法。- 分隔符要用「第一个空格」定位，因为内容里可能还有空格。凡是「前缀是标识、其余是内容」的格式，都应当用
indexOf一刀切而不是全量split。- 双关键字比较的顺序即规则的优先级：先内容后标识符。拿整条日志当排序键是最典型的错误，它等于把标识符提成了第一关键字。
- 类型判定看的是内容的首字符（第一个空格之后那个），不是整条日志的首字符，也不是最后一个字符。
- 面试视角：主动指出「大一统比较器依赖排序稳定性」这一隐患，并给出分桶方案，是这题区分度最高的一句话；面试官常追问「如果换成不稳定排序会怎样」。
易错点总结
- 用整条日志作为排序键：
["g1 act car", "a1 act car"]会按"a1..."<"g1..."排，恰好正确；但["g1 act car", "a8 act zoo"]会把a8排到g1前面，而按内容"act car"<"act zoo"，正确顺序是g1在前。- 双关键字顺序写反（先标识符后内容）：
["a8 act zoo", "a1 act car"]之外的用例上，标识符会成为主导，["b1 art can", "a1 own kit"]会输出a1在前，而正确答案是b1在前。- 让数字日志也参与排序并依赖「返回 0」：Go 的
sort.Slice不稳定，["dig1 8 1 5 1", "dig2 3 6"]可能被交换成dig2在前，违反「保持原相对顺序」。- 用
split(" ")后取第 1 段当内容："let2 own kit dig"的内容会变成"own"，与"own kit dig"的排序结果不同；含多空格的日志全部错位。- 判定类型时看整条日志的首字符：标识符总是以字母开头，所有日志都会被判成字母日志，数字日志被卷进排序，输出顺序全乱。
- 判定类型时看最后一个字符：
"let2 own kit dig"末字符是g（字母）碰巧正确，但"dig1 8 1 5 1"末字符是1（数字）也碰巧正确；一旦出现"letx a1"这类内容以字母开头却以数字结尾的日志就会误判。log.charAt(idx + 1)不做越界保护而输入含尾随空格：题目保证内容非空，但若防御性代码写成charAt(idx)会取到空格本身，Character.isDigit(' ')返回 false，所有日志都归入字母桶。- 拼接时先放数字日志：规则明确要求字母日志在前，顺序放反会让所有含两类日志的用例整体错误。
- 原地对
logs排序后再调整：破坏了输入数组，且「数字日志原相对顺序」在排序后已经丢失，无法恢复。- 用
compareTo之外的比较方式（如按长度或按字符和）：字典序要求逐字符比较，"art can"与"art zero"长度相同但按字符和比较会得出错误顺序。- 误以为数字日志之间也要按数值排序：
["dig1 8 1 5 1", "dig2 3 6"]若按数值排会把dig2提前，正确答案是保持原样。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 179. 最大数 | 中等 | 比较器不是比较元素本身，而是比较拼接结果 a+b 与 b+a 的字典序 |
| 剑指 Offer 45. 把数组排成最小的数 | 中等 | 与 179 同一套拼接比较，只是取最小方向 |
| 451. 根据字符出现频率排序 | 中等 | 需先统计频次再按频次降序重建字符串，排序键来自预处理而非原串 |
| 1356. 根据数字二进制下 1 的数目排序 | 简单 | 标准双关键字：先按 popcount 再按数值，是本题比较器结构的最简形态 |
| 56. 合并区间 | 中等 | 排序只是预处理，真正的考点在排序后的一遍扫描合并 |
| 75. 颜色分类 | 中等 | 同为「按类别分桶」，但要求原地一趟完成，用三指针替代额外容器 |