217. Log Line Sorter
A monitoring console prints lines of the form "id message": an identifier, then a single space, then the message, which may contain more spaces. For example "x7 cpu 90" has identifier x7 and message "cpu 90".
A line is a reading line when the very first character of its message is a decimal digit ('0' to '9'), and an alert line otherwise. Reorder the lines like this: all alert lines come first, followed by all reading lines. Alert lines are sorted by their message in plain lexicographic (character code) order and, when two messages are identical, by their identifier in the same order. Reading lines keep the order in which they were printed. Lines that are completely equal in the sort keys keep their original relative order.
Return the reordered lines. A line that contains no space has an empty message and counts as an alert line, and its identifier is the entire line.
Example 1
- Input:
- logs = ["x7 cpu 90","x2 77 12","b1 cpu 85","k9 disk full","x1 3 3 3","a5 cpu 85"]
- Output:
- ["a5 cpu 85","b1 cpu 85","x7 cpu 90","k9 disk full","x2 77 12","x1 3 3 3"]
- Explanation:
Alert lines are x7, b1, k9 and a5. Sorted by message: the two "cpu 85" lines (a5 before b1 by identifier), then "cpu 90", then "disk full". The reading lines x2 and x1 keep their order at the end.
Example 2
- Input:
- logs = ["q1 zeta","q2 alpha"]
- Output:
- ["q2 alpha","q1 zeta"]
- Explanation:
Both are alert lines. The message "alpha" sorts before "zeta".
Example 3
- Input:
- logs = ["z 4","a 1"]
- Output:
- ["z 4","a 1"]
- Explanation:
Both are reading lines, so they stay in the original order.
Constraints
1 ≤ logs.length ≤ 20000
Each line is up to 100 characters from the ASCII range of lowercase letters, digits and spaces. Normally a line is an identifier, a space and a message.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O(n log n * L)
- Space
- O(n * L)