LC 937. 重新排列日志文件

题目描述

这是 LeetCode 上的 937. 重新排列日志文件 ，难度为 简单。

给你一个日志数组 logs。每条日志都是以空格分隔的字串，其第一个字为字母与数字混合的 标识符 。

有两种不同类型的日志：

• 字母日志：除标识符之外，所有字均由小写字母组成
• 数字日志：除标识符之外，所有字均由数字组成

请按下述规则将日志重新排序：

• 所有 字母日志 都排在 数字日志 之前。
• 字母日志 在内容不同时，忽略标识符后，按内容字母顺序排序；在内容相同时，按标识符排序。
• 数字日志 应该保留原来的相对顺序。

返回日志的最终顺序。

示例 1：

输入：logs = ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"]

输出：["let1 art can","let3 art zero","let2 own kit dig","dig1 8 1 5 1","dig2 3 6"]

解释：
字母日志的内容都不同，所以顺序为 "art can", "art zero", "own kit dig" 。
数字日志保留原来的相对顺序 "dig1 8 1 5 1", "dig2 3 6" 。

示例 2：

输入：logs = ["a1 9 2 3 1","g1 act car","zo4 4 7","ab1 off key dog","a8 act zoo"]

输出：["g1 act car","a8 act zoo","ab1 off key dog","a1 9 2 3 1","zo4 4 7"]

提示：

• $1 <= logs.length <= 100$
• $3 <= logs[i].length <= 100$
• $logs[i]$ 中，字与字之间都用 单个 空格分隔
• 题目数据保证 $logs[i]$ 都有一个标识符，并且在标识符之后至少存在一个字

---

自定义类 + 排序

根据排序规则，我们需要对每个 $str[i]$ 进行裁剪处理，从而得知每个 $str[i]$ 是属于「字母日志」还是「数字日志」，以及得到 sign 部分和 content 部分。

在排序过程中，每个 $str[i]$ 会被访问多次，为了让每个 $str[i]$ 只进行一次这样的预处理工作，我们可以自定义类，将这部分工作放到类的实例化去做。

最后是简单将 $str[i]$ 转存成 Log 实例，自定义排序，用排序结果构造答案的基本逻辑。

代码：

class Solution {
    class Log {
        int type, idx;
        String ori, sign, content;
        Log(String s, int _idx) {
            idx = _idx;
            int n = s.length(), i = 0;
            while (i < n && s.charAt(i) != ' ') i++;
            sign = s.substring(0, i);
            content = s.substring(i + 1);
            ori = s;
            type = Character.isDigit(content.charAt(0)) ? 1 : 0;
        }
    }
    public String[] reorderLogFiles(String[] logs) {
        int n = logs.length;
        List<Log> list = new ArrayList<>();
        for (int i = 0; i < n; i++) list.add(new Log(logs[i], i));
        Collections.sort(list, (a, b)->{
            if (a.type != b.type) return a.type - b.type;
            if (a.type == 1) return a.idx - b.idx;
            return !a.content.equals(b.content) ? a.content.compareTo(b.content) : a.sign.compareTo(b.sign);
        });
        String[] ans = new String[n];
        for (int i = 0; i < n; i++) ans[i] = list.get(i).ori;
        return ans;
    }
}

• 时间复杂度：将所有的 $str[i]$ 转存成 Log 实例，复杂度为 $O(n)$；排序复杂度为 $O(n\log{n})$；构造答案复杂度为 $O(n)$。整体复杂度为 $O(n\log{n})$
• 空间复杂度：$O(n)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.937 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。