最小时间差
# 📃 题目描述
题目链接:
- 剑指 Offer II 035. 最小时间差 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
- 539. 最小时间差 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
# 🔔 解题思路
这个题目最直观的解法是求出任意两个时间的间隔,然后比较得出最小的时间差。如果输入 n 个时间,那么需要计算每个时间与另外n-1个时间的间隔,这种蛮力法需要O(n2)的时间。
上述解法的一个优化方法是把 n 个时间排序。排序之后只需要计算两两相邻的时间之间的间隔,这样就只需要计算O(n)个时间差。由于对 n 个时间进行排序通常需要O(nlogn)的时间,因此这种优化算法的总体时间复杂度是O(nlogn)。
这里有一个特殊情况值得注意。如果把输入的时间数组 ["23:50","23:59","00:00"] 排序,就可以得到["00:00","23:50","23:59"]:
时间 00:00 和 23:50 之间的间隔是 1430 分钟,而 23:50 和 23:59 之间的间隔是 9 分钟。
⭐ 由于排序之后的第 1 个时间 00:00 也可能是第 2 天的 00:00,它和前一天的 23:59 之间的间隔只有1分钟。也就是说,在计算最小时间差时,需要把排序之后的第 1 个时间当作第 2 天的时间(即加上 24 小时)与最后一个时间之间的间隔也考虑进去。
再举个例子
比如 01:00(t1) 和 23:00(t2):
- 情况 1:如果这俩是同一天,那么相差 22 个小时(这种情况肯定需要考虑的,没得说)
- 情况 2:如果 t1 在第二天,t2 在第一天,那么 t2 再经过 2 个小时就能到 t1 时间(这种情况需要考虑)
- 情况 3:如果 t1 在第一天,t2 在第二天,那么 t1 还需要 23 + 23 = 46 个小时才能到达 t2(这种情况显然不用考虑了)
接着思考如何做进一步优化。前面的算法主要将时间花在排序上面,那么排序是否可以避免?排序是为了计算相邻的两个时间的节点,所以用一个表示时间的数组也可以达到这个目的。
一天有24小时,即1440分钟。如果用一个长度为1440的数组表示一天的时间,那么数组下标为0的位置对应时间00:00,下标为1的位置对应时间00:01,以此类推,下标为1439的位置对应23:59。数组中的每个元素是true或false的标识,表示对应的时间是否存在于输入的时间数组中。
有了这个辅助数组,就只需要从头到尾扫描一遍,相邻的两个为 true 的值表示对应的两个时间在输入时间数组中是相邻的。例如,输入时间数组["23:50","23:59","00:00"],数组中只有下标为 0、1430和1439 这3个位置的值为true,其他位置的值都是 false。
由于数组的下标对应的是时间,因此两个时间之间的时间差就是它们在数组中对应的下标之差
class Solution {
public int findMinDifference(List<String> timePoints) {
boolean[] times = new boolean[1440];
for (String timePoint : timePoints) {
int minutes = transfer(timePoint);
// 如果 times[minutes] 已经置为 true, 说明出现了两个一样的时间,直接返回 0 就行了
if (times[minutes] == true) {
return 0;
}
times[minutes] = true;
}
int minLen = times.length - 1;
// 这个字段用来计算第 1 种情况(在同一天),两个连续时间 当天 的时间差
int pre = -1;
// 这两个字段是用来计算第 2 种情况的(不在同一天),第一天的时间要尽可能大,第二天的时间要尽可能小
int first = -1; // 第一天
int last = times.length - 1; // 第二天
for (int i = 0; i < times.length; i ++) {
if (times[i] == true) {
if (pre != -1) {
minLen = Math.min(minLen, i - pre);
}
pre = i;
// 第一天时间尽可能大
first = Math.max(first, i);
// 第二天时间尽可能小
last = Math.min(last, i);
}
}
return Math.min(minLen, last + times.length - first);
}
// hour -> minutes
private int transfer(String timePoint) {
String[] item = timePoint.split(":");
return Integer.parseInt(item[0]) * 60 + Integer.parseInt(item[1]);
}
}
# 💥 复杂度分析
- 空间复杂度:O(N)
- 时间复杂度:O(N)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~