KK's blog

每天积累多一些

0%

LeetCode 937 Reorder Data in Log Files

Posted on Disqus:

LeetCode



You are given an array of logs. Each log is a space-delimited string of words, where the first word is the identifier.

There are two types of logs:

Letter-logs: All words (except the identifier) consist of lowercase English letters. Digit-logs: All words (except the identifier) consist of digits.

Reorder these logs so that:

1. The letter-logs come before all digit-logs.
2. The letter-logs are sorted lexicographically by their contents. If their contents are the same, then sort them lexicographically by their identifiers.
3. The digit-logs maintain their relative ordering.

Return the final order of the logs.

Example 1:

Input: logs = [“dig1 8 1 5 1”,”let1 art can”,”dig2 3 6”,”let2 own kit dig”,”let3 art zero”]
Output: [“let1 art can”,”let3 art zero”,”let2 own kit dig”,”dig1 8 1 5 1”,”dig2 3 6”]
Explanation:
The letter-log contents are all different, so their ordering is “art can”, “art zero”, “own kit dig”.
The digit-logs have a relative order of “dig1 8 1 5 1”, “dig2 3 6”.


Example 2:

Input: logs = [“a1 9 2 3 1”,”g1 act car”,”zo4 4 7”,”ab1 off key dog”,”a8 act zoo”]
Output: [“g1 act car”,”a8 act zoo”,”ab1 off key dog”,”a1 9 2 3 1”,”zo4 4 7”]


Constraints:

1 <= logs.length <= 100 3 <= logs[i].length <= 100
All the tokens of logs[i] are separated by a single space. logs[i] is guaranteed to have an identifier and at least one word after the identifier.

题目大意：

排序log file，以下顺序：字母log (内容，id), 数字log

解题思路(推荐)：

N/A

解题步骤：

N/A

注意事项：

  1. 排序的multi key实现(0, content_str, li[0]) if is_alpha else (1, ). (1, )表示按数组顺序

Python代码：

1
2
3
4
5
6
7
8
9
def reorderLogFiles(self, logs: List[str]) -> List[str]:

	def get_key(x):
		li = x.split(' ')
		content_str = ' '.join(li[1:])
		is_alpha = 1 if content_str[0].isalpha() else 0
		return (0, content_str, li[0]) if is_alpha else (1, )

	return sorted(logs, key=get_key)

算法分析：

时间复杂度为O(nmlogn)，空间复杂度O(mn), n为log数量，m为每个log的最长长度。如mergesort中merge复杂度为nm, 每个key比较是O(m)复杂度

算法II解题思路：

我的解法。本质上和上法一致，较繁琐

注意事项：

  1. 字母log排序不能按content_str + ‘ ‘ + li[0], 而是(content_str, li[0])作多key排序

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
def reorderLogFiles2(self, logs: List[str]) -> List[str]:
	letter_logs, digit_logs = [], []
	for i in range(len(logs)):
		if logs[i][-1].isdigit():
			digit_logs.append(logs[i])
		else:
			li = logs[i].split(' ')
			content_str = ' '.join(li[1:])
			letter_logs.append((content_str, li[0], i))
	letter_logs.sort()
	res = [logs[pair[2]] for pair in letter_logs]
	res += digit_logs
	return res
Free mock interview