题目
给定一组范围在00:00至23:59的时间,求任意两个时间之间的最小时间差。例如,输入时间数组[“23:50”,“23:59”,“00:00”],"23:59"和"00:00"之间只有1分钟的间隔,是最小的时间差。
分析
这个题目最直观的解法是求出任意两个时间的间隔,然后比较得出最小的时间差。如果输入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小时)与最后一个时间之间的间隔也考虑进去。
接着思考如何做进一步优化。前面的算法主要将时间花在排序上面,那么排序是否可以避免?排序是为了计算相邻的两个时间的节点,所以用一个表示时间的数组也可以达到这个目的。
一天有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。文章来源:https://www.toymoban.com/news/detail-740849.html
由于数组的下标对应的是时间,因此两个时间之间的时间差就是它们在数组中对应的下标之差。23:50和23:59之间相隔9分钟,它们在数组中的下标之差也是9。文章来源地址https://www.toymoban.com/news/detail-740849.html
解
public class Test {
public static void main(String[] args) {
List<String> timePoints = Arrays.asList("23:50", "23:59", "00:00");
int result = findMinDifference(timePoints);
System.out.println(result);
}
public static int findMinDifference(List<String> timePoints) {
if (timePoints.size() > 1440) {
return 0;
}
boolean[] minuteFlags = new boolean[1440];
for (String time : timePoints) {
String[] t = time.split(":");
int min = Integer.parseInt(t[0]) * 60 + Integer.parseInt(t[1]);
if (minuteFlags[min]) {
return 0;
}
minuteFlags[min] = true;
}
return helper(minuteFlags);
}
private static int helper(boolean[] minuteFlags) {
int minDiff = minuteFlags.length - 1;
int prev = -1;
int first = minuteFlags.length - 1;
int last = -1;
for (int i = 0; i < minuteFlags.length; i++) {
if (minuteFlags[i]) {
if (prev >= 0) {
minDiff = Math.min(i - prev, minDiff);
}
prev = i;
first = Math.min(i, first);
last = Math.max(i, last);
}
}
minDiff = Math.min(first + minuteFlags.length - last, minDiff);
return minDiff;
}
}
到了这里,关于面试算法35:最小时间差的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!