网络异常,图片无法展示
|
题目描述
这是 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 原题链接和其他优选题解。