leetcode
leetcode 501 ~ 550
最小时间差

最小时间差

难度:

标签:

题目描述

给定一个 24 小时制(小时:分钟 "HH:MM")的时间列表,找出列表中任意两个时间的最小时间差并以分钟数表示。

 

示例 1:

输入:timePoints = ["23:59","00:00"]
输出:1

示例 2:

输入:timePoints = ["00:00","23:59","00:00"]
输出:0

 

提示:

  • 2 <= timePoints.length <= 2 * 104
  • timePoints[i] 格式为 "HH:MM"

代码结果

运行时间: 26 ms, 内存: 18.2 MB


/*
题目思路:
1. 使用Java Stream API对时间点进行转换和处理。
2. 将所有时间点转换为分钟数。
3. 对转换后的分钟数组进行排序。
4. 计算相邻时间点的时间差,并更新最小差值。
5. 特别注意首尾时间点的时间差(跨越午夜)。
6. 返回最小时间差。
*/
 
import java.util.List;
import java.util.stream.Collectors;
 
public class SolutionStream {
    public int findMinDifference(List<String> timePoints) {
        // 将时间点转换为分钟并排序
        List<Integer> minutes = timePoints.stream()
                .map(time -> Integer.parseInt(time.split(":")[0]) * 60 + Integer.parseInt(time.split(":")[1]))
                .sorted()
                .collect(Collectors.toList());
        // 初始化最小差值为一天的最大分钟数
        int minDiff = 1440;
        for (int i = 1; i < minutes.size(); i++) {
            // 计算相邻时间点的差值
            minDiff = Math.min(minDiff, minutes.get(i) - minutes.get(i - 1));
        }
        // 计算首尾时间点跨越午夜的差值
        minDiff = Math.min(minDiff, 1440 - minutes.get(minutes.size() - 1) + minutes.get(0));
        return minDiff;
    }
}
 

解释

方法:

这个题解的思路是先将时间字符串转换为以分钟为单位的整数,然后对转换后的分钟数进行排序。接下来,计算相邻时间之间的差值,找出最小差值。同时还需要考虑第一个时间和最后一个时间之间的差值,因为时间是循环的。最后返回最小差值作为结果。

时间复杂度:

O(n log n)

空间复杂度:

O(n)

代码细节讲解

🦆
题解中提到最小差值初始设置为 `float('inf')`,为什么选择这个值作为初始最小差值,并且这种做法有什么优点或潜在的问题?
在算法中,将最小差值初始化为 `float('inf')` 是一种常见的技巧,用于确保任何后续比较过程中的差值都会小于这个初始值。这样做的主要优点是简化了代码逻辑,避免了需要额外判断是否是第一次计算差值的情况。此外,`float('inf')` 表示无穷大,这确保了在开始比较之前,任何实际的差值都会被更新为最小差值。然而,这种做法也有潜在的问题,比如在处理极大的数据集时,可能会引起数值稳定性和性能问题。此外,如果在某些特殊情况下差值计算错误导致没有比 `float('inf')` 更小的值出现,那么算法可能会错误地返回 `float('inf')`,从而掩盖了错误。

相关问题