LeetCode 937. 重新排列日志文件

约 5 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 携程
标签
数组 字符串 排序

题目描述

✅ 937. 重新排列日志文件

image-20260929105255616

image-20260929105255746

题意分析

每条日志的第一个单词是标识符，其余部分是内容。要先放全部字母日志，再放数字日志；字母日志按完整内容的字典序排序，内容相同时再比较标识符；数字日志则保留原来的相对顺序。

解法：分桶 + 排序（字母日志）+ 稳定拼接

核心思路

[!blue]

先按输入顺序扫描，将日志分到 letters 和 digits 两个列表。第一个空格分隔标识符与内容，题目保证内容非空且要么全是字母单词、要么全是数字单词，因此只看空格后的第一个字符就能区分类型，不能根据标识符判断。

数字日志在收集时保持原顺序，之后不再参与排序。字母日志则使用两个排序关键字：先比较首个空格之后的全部内容，只有内容完全相同，才比较空格之前的标识符。比较的是字典序，不需要把数字日志解析为数值。

最后依次输出排序后的 letters 与原顺序的 digits。拼接顺序保证字母在前，字母列表的比较器保证两级排序，数字列表从未被打乱则保证稳定性。三条要求分别得到满足，每条原日志又只被收集和输出一次，因此没有遗漏或重复。

解题步骤

  1. 定位首个空格，根据内容字符区分日志类型。
  2. 按原顺序收集两类日志。
  3. 字母日志按内容与标识符排序。
  4. 先输出字母日志，再接数字日志。

只有数字日志时，结果与输入顺序相同；只有字母日志时，只需完成内容与标识符排序。内容和标识符都相同的日志本身相同，彼此的先后不影响结果。

代码实现

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;
    }
}

import "sort"

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
}

复杂度分析

  • 时间复杂度：设输入总字符数 S、字母日志数 W、最大日志长度 L，时间为 $O(S+WL\log(W+1))$。
  • 空间复杂度：列表、输出引用和排序工作区合计为 $O(n)$；Java 比较器创建的临时子串还需 $O(L)$ 峰值空间，因此 Java 上界为 $O(n+L)$，Go 为 $O(n)$。

关键点总结

[!green]

  • 比较的第一关键字是内容，不是整条日志。
  • 数字日志不参与排序，原顺序自然保留。
  • 首个空格之后的全部文本都属于内容。

易错点总结

[!yellow]

  • 直接排序整条字符串，会让标识符错误地成为第一关键字。
  • 内容包含首个空格之后的所有单词，不能只比较第一个内容单词。
  • 数字日志不能按数值或字典序排序，它们只保留输入中的相对顺序。
  • 只有完整内容相同，才启用标识符这个第二关键字。

相似题目

题目 难度 关联与区别
791. 自定义字符串排序 中等 同样自定义排序规则，本题先按日志类型分组，再按内容和标识符比较，并保留数字日志相对顺序。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/29612243
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！