难度: Medium
给定一个 24 小时制（小时:分钟 "HH:MM"）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。
示例 1：
输入：timePoints = ["23:59","00:00"] 输出：1
示例 2：
输入：timePoints = ["00:00","23:59","00:00"] 输出：0
提示：
2 <= timePoints.length <= 2 * 104timePoints[i]格式为 "HH:MM"
Submission
运行时间: 26 ms
内存: 18.2 MB
from typing import List
class Solution:
def findMinDifference(self, timePoints: List[str]) -> int:
# Convert time to minutes
def time_to_minutes(time: str) -> int:
hours, minutes = map(int, time.split(":"))
return hours * 60 + minutes
# Check for duplicates
if len(set(timePoints)) < len(timePoints):
return 0
# Convert times to minutes and sort
minutes = sorted(time_to_minutes(time) for time in timePoints)
# Calculate minimum difference
min_diff = float("inf")
for i in range(1, len(minutes)):
diff = minutes[i] - minutes[i-1]
min_diff = min(min_diff, diff)
# Consider the difference between the last and the first time
circular_diff = (24 * 60 - minutes[-1] + minutes[0]) % (24 * 60)
min_diff = min(min_diff, circular_diff)
return min_diff
Explain
这个题解的思路是先将时间字符串转换为以分钟为单位的整数，然后对转换后的分钟数进行排序。接下来，计算相邻时间之间的差值，找出最小差值。同时还需要考虑第一个时间和最后一个时间之间的差值，因为时间是循环的。最后返回最小差值作为结果。
时间复杂度: O(n log n)
空间复杂度: O(n)
from typing import List
class Solution:
def findMinDifference(self, timePoints: List[str]) -> int:
# 将时间转换为分钟数
def time_to_minutes(time: str) -> int:
hours, minutes = map(int, time.split(":"))
return hours * 60 + minutes
# 检查是否有重复的时间
if len(set(timePoints)) < len(timePoints):
return 0
# 将时间转换为分钟数并排序
minutes = sorted(time_to_minutes(time) for time in timePoints)
# 计算最小差值
min_diff = float("inf")
for i in range(1, len(minutes)):
diff = minutes[i] - minutes[i-1]
min_diff = min(min_diff, diff)
# 考虑第一个时间和最后一个时间之间的差值
circular_diff = (24 * 60 - minutes[-1] + minutes[0]) % (24 * 60)
min_diff = min(min_diff, circular_diff)
return min_diff
Explore
在算法中，将最小差值初始化为 `float('inf')` 是一种常见的技巧，用于确保任何后续比较过程中的差值都会小于这个初始值。这样做的主要优点是简化了代码逻辑，避免了需要额外判断是否是第一次计算差值的情况。此外，`float('inf')` 表示无穷大，这确保了在开始比较之前，任何实际的差值都会被更新为最小差值。然而，这种做法也有潜在的问题，比如在处理极大的数据集时，可能会引起数值稳定性和性能问题。此外，如果在某些特殊情况下差值计算错误导致没有比 `float('inf')` 更小的值出现，那么算法可能会错误地返回 `float('inf')`，从而掩盖了错误。