LeetCode Weekly Contest 23 之 539. Minimum Time Difference
LeetCode Weekly Contest 23 之 539. Minimum Time Difference
LeetCode Weekly Contest 23
赛题
本次周赛主要分为以下4道题：
- 541 Reverse String II (3分)
- 539 Minimum Time Difference (5分)
- 536 Construct Binary Tree from String (6分)
- 527 Word Abbreviation (8分)
539 Minimum Time Difference
Problem:
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
Input: [“23:59”,”00:00”] Output: 1
Note
1 The number of time points in the given list is at least 2 and won’t exceed 20000. 2 The input time is legal and ranges from 00:00 to 23:59.
这是一道中等难度的题，但我觉得破解它并不难，而且实际的AC率也高达50%，当时在思考时，觉得难点主要在于对0点这个点该怎么区分，而恰恰Example中给出了这样的例子，否则还真的不会注意到要区分0点。
所以还是AC了，分享下自己的思考过程吧，我看到时钟之间的差，第一个想到的是每个timepoints分布在了一个圆圈上，无非就是求两个相邻point的最小间隔罢了。但有个问题时，在圆的0时刻上，该怎么判断呢？
首先求points之间的最小间隔，那么points 最好是有序的。那么我就把所有的points依次排序在圆圈上就好了，0时刻有点蛋疼，但我想到的是把圆拉成一条线，呵呵，不就是一个数组么，无非再让最后一个元素和头一个元素再比较一下就好了，就形成了一个环的min diff。So
My first solution(37ms)
public int findMinDifference(List<String> timePoints) {
int[] times = new int[timePoints.size()];
int index = 0;
for (String num : timePoints){
String[] time = num.split(":");
int minutes = Integer.parseInt(time[0]) * 60 + Integer.parseInt(time[1]);
times[index++] = minutes;
}
Arrays.sort(times);
int min = Integer.MAX_VALUE;
for (int i = 1; i < times.length; i++){
if(times[i] - times[i-1] < min){
min = times[i] - times[i-1];
}
}
//最后一个数
if ((times[0] + 24 * 60 )- times[times.length -1] < min){
min = (times[0] + 24 * 60 )- times[times.length -1];
}
return min;
}String 转下int数组，方便后期进行diff操作，该算法的时间复杂度为O(nlgn)O(n lgn)，先对times数组中的头置尾的元素操作，最后比较一次尾和头的元素，但尾头元素，注意要加上一个1440的值，其他没什么。
可优化空间： 1. int型的times数组其实没必要，浪费了空间。 2. 最后一个数的比较和前n-1个数的比较不能写到一块么？
My second solution(44ms)
public int findMinDifference(List<String> timePoints) {
int[] times = new int[timePoints.size()];
int index = 0;
for (String num : timePoints) {
String[] time = num.split(":");
int minutes = Integer.parseInt(time[0]) * 60 + Integer.parseInt(time[1]);
times[index++] = minutes;
}
Arrays.sort(times);
int min = Integer.MAX_VALUE;
int prev = times[times.length-1];
for (int i = 0; i < times.length; i++){
int diff = (times[i] - prev);
if(diff < 0) diff += 1440;
min = Math.min(min, diff);
prev = times[i];
}
return min;
}呵呵，添加了一个prev指针后，实现了最后元素和前n-1个元素的合并，的确蛮巧妙的，算是算法细节吧，真正做题哪顾得上那么多啊。但这里的循环检验着实是一个好的想法，起码构成了一个loop的diff问题吧！注意for循环中的if判断，难道是它影响了运行时间！！！还没优化空间呢，其实有了prev，空间优化的思路已经出来了，直接遍历timePoints解析呗。
My third solution(97ms)
public int findMinDifference(List<String> timePoints) {
public int findMinDifference(List<String> timePoints) {
Collections.sort(timePoints);
int minDiff = Integer.MAX_VALUE;
String prev = timePoints.get(timePoints.size() - 1);
for (String s : timePoints) {
int prevMins = Integer.parseInt(prev.split(":")[0]) * 60 + Integer.parseInt(prev.split(":")[1]);
int curMins = Integer.parseInt(s.split(":")[0]) * 60 + Integer.parseInt(s.split(":")[1]);
int diff = curMins - prevMins;
if (diff < 0)
diff += 1440;
minDiff = Math.min(minDiff, diff);
prev = s;
}
return minDiff;
}原来，Collections可以直接对timePoints排序啊,真是看了答案才知道的。空间复杂度下降了，但运行时间反而升了。我能想到的就这里了，但在赛题复盘时，发现还有个O(n)解，处于好奇，咱继续研究下。
针对一个排序算法它能形成O(n)解的情况，只能是一个利用有限大小的位置做bucket排序，这让我在解排序问题时，给出了一个新的思考角度，如果是排序，请先思考能否bucket排序，能否bucket排序，能否bucket排序。分钟能出现的位置只能是从[0-1439]中间的任何位置，So
My forth solution(19ms)
public int findMinDifference(List<String> timePoints) {
boolean[] timeSeen = new boolean[1440];
for (String s : timePoints) {
int mins = Integer.parseInt(s.split(":")[0]) * 60 + Integer.parseInt(s.split(":")[1]);
if (timeSeen[mins])
return 0;
timeSeen[mins] = true;
}
int minDiff = Integer.MAX_VALUE,prev = 0;
for (int i = 1439; i >= 0; i--){
if(timeSeen[i]){
prev = i;
break;
}
}
for (int i = 0; i < 1440; i++) {
if(timeSeen[i]){
int diff = i - prev;
if(diff <0) diff += 1440;
minDiff = Math.min(minDiff, diff);
prev = i;
}
}
return minDiff;
}沿用第三种prev的解决方案，我们现在无非就是把它进过一次遍历就放在了指定的位置上，同样的先找出尾部的第一个True元素，与第0个元素比较，剩余元素均与前一个True元素比较，取最小的diff，即为我们的答案。