[每日一题]剑指Offer II035.最小时间差
剑指 Offer II 035. 最小时间差 给定一个 24 小时制（小时:分钟 “HH:MM”）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。
输入：timePoints = [“23:59”,”00:00”] 输出：1
输入：timePoints = [“00:00”,”23:59”,”00:00”] 输出：0
提示：
- 2 <= timePoints <= 2 * 104
- timePoints[i] 格式为 “HH:MM”
Solutions
class Solution {
public int findMinDifference(List<String> timePoints) {
if (timePoints.size() > 24 * 60) {
return 0;
}
List<Integer> mins = new ArrayList<>();
for (String t : timePoints) {
String[] time = t.split(":");
mins.add(Integer.parseInt(time[0]) * 60 + Integer.parseInt(time[1]));
}
Collections.sort(mins);
mins.add(mins.get(0) + 24 * 60);
int res = 24 * 60;
for (int i = 1; i < mins.size(); ++i) {
res = Math.min(res, mins.get(i) - mins.get(i - 1));
}
return res;
}
}
class Solution {// 排序
public int findMinDifference(List<String> timePoints) {
Collections.sort(timePoints);
int ans = Integer.MAX_VALUE;
int t0Minutes = getMinutes(timePoints.get(0));
int preMinutes = t0Minutes;
for (int i = 1; i < timePoints.size(); ++i) {
int minutes = getMinutes(timePoints.get(i));
ans = Math.min(ans, minutes - preMinutes); // 相邻时间的时间差
preMinutes = minutes;
}
ans = Math.min(ans, t0Minutes + 1440 - preMinutes); // 首尾时间的时间差
return ans;
}
public int getMinutes(String t) {
return ((t.charAt(0) - '0') * 10 + (t.charAt(1) - '0')) * 60 + (t.charAt(3) - '0') * 10 + (t.charAt(4) - '0');
}
}
class Solution {// 鸽巢原理
public int findMinDifference(List<String> timePoints) {
int n = timePoints.size();
if (n > 1440) {
return 0;
}
Collections.sort(timePoints);
int ans = Integer.MAX_VALUE;
int t0Minutes = getMinutes(timePoints.get(0));
int preMinutes = t0Minutes;
for (int i = 1; i < n; ++i) {
int minutes = getMinutes(timePoints.get(i));
ans = Math.min(ans, minutes - preMinutes); // 相邻时间的时间差
preMinutes = minutes;
}
ans = Math.min(ans, t0Minutes + 1440 - preMinutes); // 首尾时间的时间差
return ans;
}
public int getMinutes(String t) {
return ((t.charAt(0) - '0') * 10 + (t.charAt(1) - '0')) * 60 + (t.charAt(3) - '0') * 10 + (t.charAt(4) - '0');
}
}
Ideas
-
方法一：排序 将 timePoints 排序后，最小时间差必然出现在 timePoints 的两个相邻时间，或者 timePoints 的两个首尾时间中。因此排序后遍历一遍 timePoints 即可得到最小时间差。
-
方法二：鸽巢原理 根据题意，一共有 24×60=1440 种不同的时间。由鸽巢原理可知，如果timePoints 的长度超过 1440，那么必然会有两个相同的时间，此时可以直接返回 0。