网络异常，图片无法展示
|
题目描述
这是 LeetCode 上的 937. 重新排列日志文件 ，难度为 简单。
Tag : 「排序」
给你一个日志数组 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 <= 1001<=logs.length<=100
- 3 <= logs[i].length <= 1003<=logs[i].length<=100
- logs[i]logs[i] 中，字与字之间都用 单个 空格分隔
- 题目数据保证 logs[i]logs[i] 都有一个标识符，并且在标识符之后至少存在一个字
自定义类 + 排序
根据排序规则，我们需要对每个 str[i]str[i] 进行裁剪处理，从而得知每个 str[i]str[i] 是属于「字母日志」还是「数字日志」，以及得到 sign 部分和 content 部分。
在排序过程中，每个 str[i]str[i] 会被访问多次，为了让每个 str[i]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]str[i] 转存成
Log实例，复杂度为 O(n)O(n)；排序复杂度为 O(n\log{n})O(nlogn)；构造答案复杂度为 O(n)O(n)。整体复杂度为 O(n\log{n})O(nlogn) - 空间复杂度：O(n)O(n)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.937 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
