当前位置：首页 > web >正文

华为OD机试_2025 B卷_运维日志排序（Python，100分）（附详细解题思路）

web 2025/6/17 11:48:54

题目描述

运维工程师采集到某产品线网运行一天产生的日志n条，现需根据日志时间先后顺序对日志进行排序，日志时间格式为H:M:S.N。
• H表示小时(0~23)
• M表示分钟(0~59)
• S表示秒(0~59)
• N表示毫秒(0~999)
时间可能并没有补全，也就是说，01:01:01.001也可能表示为1:1:1.1。

输入描述
第一行输入一个整数n表示日志条数，1<=n<=100000，接下来n行输入n个时间。

输出描述
按时间升序排序之后的时间，如果有两个时间表示的时间相同，则保持输入顺序。

用例

输入

2
01:41:8.9
1:1:09.211

输出

1:1:09.211

01:41:8.9

说明

无

输入

3
23:41:08.023
1:1:09.211
08:01:22.0

输出

1:1:09.211

08:01:22.0

23:41:08.023

说明

无

输入

2
22:41:08.023
22:41:08.23

输出

22:41:08.023

22:41:08.23

说明

两个时间表示的时间相同，保持输入顺序

时间日志排序算法详解

核心解题思路

本题目要求对格式为H:M:S.N的时间日志进行排序，其中时间可能没有补全（如1:1:1.1表示01:01:01.100）。解题的核心思路如下：

时间格式解析：将非标准化时间字符串分解为小时、分钟、秒和毫秒四个部分
单位统一转换：将所有时间单位转换为毫秒以便比较
稳定排序：在排序过程中，对于时间相同的条目保持原始输入顺序
结果输出：输出原始时间字符串（不改变其格式）

关键点说明

补全规则：对于毫秒部分，如果位数不足3位，需要在右侧补零（如1→100，01→010）
排序稳定性：使用稳定排序算法，确保时间相同时保持输入顺序
高效处理：采用O(n log n)的排序算法处理最多100,000条日志

完整代码实现

def main():n = int(input().strip())times = [input().strip() for _ in range(n)]# 存储(总毫秒数，原始字符串)的元组parsed_times = []for time_str in times:# 分割小时、分钟和秒/毫秒部分parts = time_str.split(':')hour = int(parts[0])minute = int(parts[1])# 处理秒和毫秒if '.' in parts[2]:sec_str, ms_str = parts[2].split('.', 1)  # 只分割一次sec = int(sec_str)# 毫秒处理：截取前3位并右侧补零ms_str = ms_str[:3].ljust(3, '0')ms = int(ms_str)else:sec = int(parts[2])ms = 0# 计算总毫秒数total_ms = (hour * 3600 + minute * 60 + sec) * 1000 + msparsed_times.append((total_ms, time_str))# 稳定排序（时间相同的保持输入顺序）parsed_times.sort(key=lambda x: x[0])# 输出结果for _, time_str in parsed_times:print(time_str)if __name__ == "__main__":main()

算法原理解析

1. 时间解析

parts = time_str.split(':')
hour = int(parts[0])
minute = int(parts[1])

使用冒号分割字符串获取小时和分钟
直接转换为整数（自动处理前导零）

2. 秒和毫秒处理

if '.' in parts[2]:sec_str, ms_str = parts[2].split('.', 1)ms_str = ms_str[:3].ljust(3, '0')ms = int(ms_str)

检查秒部分是否包含小数点（表示有毫秒）
分割秒和毫秒部分
关键操作：毫秒字符串右侧补零至3位（如9→900，09→090）
转换为整数的毫秒值

3. 毫秒转换公式

total_ms = (hour * 3600 + minute * 60 + sec) * 1000 + ms

1小时 = 3600秒 = 3,600,000毫秒
1分钟 = 60秒 = 60,000毫秒
1秒 = 1,000毫秒
公式汇总：(小时×3600 + 分钟×60 + 秒)×1000 + 毫秒

4. 稳定排序

parsed_times.sort(key=lambda x: x[0])

使用Python的TimSort（稳定排序算法）
仅比较总毫秒数，时间相同时保持原始顺序
时间复杂度O(n log n)，满足100,000条日志的处理需求

示例解析

示例1：输入`2\n01:41:8.9\n1:1:09.211`

解析第一条：01:41:8.9
- 小时=1, 分钟=41, 秒=8, 毫秒=900（9→900）
- 总毫秒 = (1×3600 + 41×60 + 8)×1000 + 900 = 6,068,900
解析第二条：1:1:09.211
- 小时=1, 分钟=1, 秒=9, 毫秒=211
- 总毫秒 = (1×3600 + 1×60 + 9)×1000 + 211 = 3,669,211
排序结果：3,669,211 < 6,068,900 → 先输出第二条
```
1:1:09.211
01:41:8.9
```

示例2：输入`3\n23:41:08.023\n1:1:09.211\n08:01:22.0`

解析：
- 1:1:09.211 → 3,669,211
- 08:01:22.0 → (8×3600 + 1×60 + 22)×1000 + 0 = 28,882,000
- 23:41:08.023 → (23×3600 + 41×60 + 8)×1000 + 23 = 85,268,023
排序结果：
```
1:1:09.211
08:01:22.0
23:41:08.023
```