Medium

题目描述

给你一个日志数组 logs。每条日志都是以空格分隔的字符串，其中第一个单词是标识符。

有两种不同类型的日志：

  • 字母日志：除标识符之外，所有单词都由小写英文字母组成
  • 数字日志：除标识符之外，所有单词都由数字组成

重新排列日志，使得：

  1. 所有 字母日志 都排在 数字日志 之前
  2. 字母日志 按内容的字典序排序；如果内容相同，则按标识符的字典序排序
  3. 数字日志 应该保持原来的相对顺序

返回日志的最终顺序。

示例 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] 都有一个标识符，并且在标识符之后至少存在一个单词

解题思路

这是一道排序题，需要根据日志类型和内容进行自定义排序。

解题思路：

  1. 识别日志类型：通过检查第一个空格后的字符是否为数字来区分字母日志和数字日志
  2. 分离处理：将日志分为字母日志和数字日志两类分别处理
  3. 排序规则：
    • 字母日志需要按内容字典序排序，内容相同时按标识符排序
    • 数字日志保持原始相对顺序
  4. 合并结果：将排序后的字母日志和保持原序的数字日志合并

实现方案：

  • 方案一：分离后排序再合并
  • 方案二：使用自定义比较器统一排序（推荐）

方案二更简洁，利用自定义比较器一次性完成排序：

  • 字母日志优先级高于数字日志
  • 字母日志之间按内容比较，内容相同按标识符比较
  • 数字日志之间保持稳定排序（原始顺序）

时间复杂度为 O(n log n)，其中 n 为日志数量。

代码实现

class Solution {
public:
    vector<string> reorderLogFiles(vector<string>& logs) {
        sort(logs.begin(), logs.end(), [](const string& a, const string& b) {
            int spaceA = a.find(' ');
            int spaceB = b.find(' ');
            
            string idA = a.substr(0, spaceA);
            string idB = b.substr(0, spaceB);
            string contentA = a.substr(spaceA + 1);
            string contentB = b.substr(spaceB + 1);
            
            bool isLetterA = isalpha(contentA[0]);
            bool isLetterB = isalpha(contentB[0]);
            
            if (isLetterA && isLetterB) {
                if (contentA != contentB) {
                    return contentA < contentB;
                }
                return idA < idB;
            }
            
            if (isLetterA && !isLetterB) {
                return true;
            }
            
            if (!isLetterA && isLetterB) {
                return false;
            }
            
            return false; // 两个都是数字日志，保持稳定排序
        });
        
        return logs;
    }
};

class Solution:
    def reorderLogFiles(self, logs: List[str]) -> List[str]:
        def compare(log):
            parts = log.split(' ', 1)
            identifier, content = parts[0], parts[1]
            
            if content[0].isalpha():
                # 字母日志：返回 (0, content, identifier) 确保优先级和排序规则
                return (0, content, identifier)
            else:
                # 数字日志：返回 (1,) 确保在字母日志之后，且保持稳定排序
                return (1,)
        
        return sorted(logs, key=compare)

public class Solution {
    public string[] ReorderLogFiles(string[] logs) {
        Array.Sort(logs, (a, b) => {
            int spaceA = a.IndexOf(' ');
            int spaceB = b.IndexOf(' ');
            
            string idA = a.Substring(0, spaceA);
            string idB = b.Substring(0, spaceB);
            string contentA = a.Substring(spaceA + 1);
            string contentB = b.Substring(spaceB + 1);
            
            bool isLetterA = char.IsLetter(contentA[0]);
            bool isLetterB = char.IsLetter(contentB[0]);
            
            if (isLetterA && isLetterB) {
                int contentCompare = string.Compare(contentA, contentB);
                if (contentCompare != 0) {
                    return contentCompare;
                }
                return string.Compare(idA, idB);
            }
            
            if (isLetterA && !isLetterB) {
                return -1;
            }
            
            if (!isLetterA && isLetterB) {
                return 1;
            }
            
            return 0; // 两个都是数字日志，保持稳定排序
        });
        
        return logs;
    }
}

var reorderLogFiles = function(logs) {
    return logs.sort((a, b) => {
        const spaceA = a.indexOf(' ');
        const spaceB = b.indexOf(' ');
        
        const idA = a.substring(0, spaceA);
        const idB = b.substring(0, spaceB);
        const contentA = a.substring(spaceA + 1);
        const contentB = b.substring(spaceB + 1);
        
        const isLetterA = /^[a-z]/.test(contentA);
        const isLetterB = /^[a-z]/.test(contentB);
        
        if (isLetterA && isLetterB) {
            if (contentA !== contentB) {
                return contentA.localeCompare(contentB);
            }
            return idA.localeCompare(idB);
        }
        
        if (isLetterA && !isLetterB) {
            return -1;
        }
        
        if (!isLetterA && isLetterB) {
            return 1;
        }
        
        return 0; // 两个都是数字日志，保持稳定排序
    });
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型时间复杂度空间复杂度
整体复杂度O(n log n × m)O(1)

说明：

  • 时间复杂度：O(n log n × m)，其中 n 是日志数量，m 是日志的平均长度。排序需要 O(n log n) 次比较，每次字符串比较需要 O(m) 时间
  • 空间复杂度：O(1)，原地排序，只使用常数额外空间（不考虑排序算法本身的递归栈空间）