What is the main idea behind Reorder Data in Log Files?

The key idea is to separate letter-logs from digit-logs, sort letter-logs lexicographically, then append digit-logs in their original order.

How do I handle ties when two letter-logs have the same content?

Use the identifiers as tie-breakers to determine the relative order between logs with identical content.

Can I sort digit-logs as well?

No, digit-logs must retain their original relative order according to the problem's requirements.

What is the time complexity of the solution?

The solution runs in O(M * N * log N) time, where N is the number of logs and M is the maximum length of a log content.

Which data structure helps manage letter-log and digit-log separation efficiently?

Using two separate lists or arrays ensures letter-logs can be sorted independently without affecting digit-logs.

#937

Medium

auto_awesome数组·string

LeetCode 题解工作台

重新排列日志文件

给你一个日志数组 logs 。每条日志都是以空格分隔的字串，其第一个字为字母与数字混合的标识符。有两种不同类型的日志：字母日志：除标识符之外，所有字均由小写字母组成数字日志：除标识符之外，所有字均由数字组成请按下述规则将日志重新排序：所有字母日志都排在数字日志之前。字母日…

数组字符串排序

题目描述

给你一个日志数组 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] 都有一个标识符，并且在标识符之后至少存在一个字

lightbulb

解题思路

方法一：自定义排序

我们可以使用自定义排序的方法，将日志分为两类：字母日志和数字日志。

对于字母日志，我们需要按照题目要求进行排序，即先按内容排序，再按标识符排序。

对于数字日志，我们只需要保留原来的相对顺序。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是日志的数量。

1

2

3

4

5

6

7

8

class Solution:
    def reorderLogFiles(self, logs: List[str]) -> List[str]:
        def f(log: str):
            id_, rest = log.split(" ", 1)
            return (0, rest, id_) if rest[0].isalpha() else (1,)

        return sorted(logs, key=f)

speed

复杂度分析

指标	值
时间	complexity is O(M * N * log N) because sorting letter-logs requires comparing strings of average length M over N logs. Space complexity is O(M * N) to store separated lists and handle string comparisons.
空间	\mathcal{O}(M \cdot N)

psychology

面试官常问的追问

外企场景

question_mark
Are you maintaining the relative order of digit-logs?
question_mark
Can you efficiently sort based on content while handling tie-breakers?
question_mark
How do you handle logs that have identical contents but different identifiers?

warning

常见陷阱

外企场景

error
Sorting digit-logs accidentally along with letter-logs, which breaks relative order.
error
Using only identifiers for sorting letter-logs instead of the full content.
error
Failing to split logs correctly when a log contains both letters and numbers in content.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Reorder logs but reverse the lexicographical order of letter-logs while keeping digit-logs stable.
arrow_right_alt
Reorder logs allowing mixed content but only prioritizing logs starting with letters.
arrow_right_alt
Reorder logs in-place without using extra space for separated lists.

help

常见问题

外企场景

继续练习

#893 特殊等价字符串组 #833 字符串中的查找与替换 #1048 最长字符串链