539. Minimum Time Difference
Description
Given a list of 24-hour clock time points in “Hour:Minutes” format, find the minimum minutes difference between any two time points in the list.
Example 1:
Input: ["23:59","00:00"]
Output: 1
Note:
The number of time points in the given list is at least 2 and won’t exceed 20000.
The input time is legal and ranges from 00:00 to 23:59.
此题的要求是，需要我们在一个代表若干时间点的字符串列表中，找到相差最小的两个时间点的差值。
最直接的方式就是计算所有时间点距离零点所过去的分钟数，并进行排序，再计算两两之差。取最小即可，此种方式在时间和空间上的消耗都是比较大的，而且没有利用题目中的条件进行进一步的分析。
而比较好的做法是：
因为24个小时所对应的时间点只有24*60种，也就是1440种。所以完全可以建立一个boolean数组，用来标记状态。
-
先将所有的时间点转化为分钟的形式，对新列表进行遍历，之后，如果在第i分钟时，时间点存在，则将其设置为
true，否则保持false在标记过程中，若发现某元素已经存在，直接返回0即可，因为相同时间点如果出现两次及以上，说明最小时间差就是0 -
加入辅助变量
last,first,min,prev,分别用于标记循环的左右边界和最小值以及上一次遍历过的元素。 -
之后再次遍历
boolean数组，如果first不等于初始值，则说明被更新过，那么首先计算新的min值，之后更新其他辅助变量即可。
4.返回最终结果
代码如下：
public class Solution {
public int parseTime(List<String> timePoints){
boolean [] array=new boolean[24*60];
int min=Integer.MAX_VALUE;
int first=Integer.MAX_VALUE;
int last=Integer.MIN_VALUE;
int prev=0;
for(int i=0;i<timePoints.size();++i){
String firHour=timePoints.get(i).split(":")[0];
String firMin=timePoints.get(i).split(":")[1];
int fir_Min=Integer.parseInt(firMin);
int fir_Hour=Integer.parseInt(firHour);
if(array[fir_Hour*60+fir_Min]==true) return 0;
array[fir_Hour*60+fir_Min]=true;
}
for(int i=0;i<24*60;++i){
if(array[i]){
if(first!=Integer.MAX_VALUE){
min=Math.min(min,i-prev);
}
first=Math.min(first,i);
last=Math.max(last,i);
prev=i;
}
}
return Math.min(min,24*60-last+first);
}
public int findMinDifference(List<String> timePoints) {
return parseTime(timePoints);
}
}
迭代过程如下:
输入为
["23:56","09:03","10:01"]
第543次迭代所得的first为543, last为543
第543次迭代所得的prev为543
第601次迭代所得的最小值为58
第601次迭代所得的first为543, last为601
第601次迭代所得的prev为601
第1436次迭代所得的最小值为58
第1436次迭代所得的first为543, last为1436
第1436次迭代所得的prev为1436
所得的最小值为58