539. Minimum Time Difference

发表于 | 分类于

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.

解法1： O(NlogN)

很直观的就是把array转化为分钟数的数组，然后两两比较，同时别忘了比较头和尾巴。

C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
    public int findMinDifference(List<String> timePoints) {
        if (timePoints == null || timePoints.size() == 0) {
            return 0;
        }
        int[] times = new int[timePoints.size()];
        for (int i = 0; i < timePoints.size(); i++) {
            int seperator = timePoints.get(i).indexOf(":");
            int hour = Integer.parseInt(timePoints.get(i).substring(0, seperator));
            int minute = Integer.parseInt(timePoints.get(i).substring(seperator + 1));
            times[i] = hour * 60 + minute;
        }
        Arrays.sort(times);
        int res = Integer.MAX_VALUE;
        int time24 = 24 * 60;
        for (int i = 0; i < times.length - 1; i++) {
            res = Math.min(res, Math.min(Math.abs(time24 + times[i] - times[i + 1]), Math.abs(times[i+1] - times[i])));
        }
        res = Math.min(res, Math.min(Math.abs(time24 + times[0] - times[times.length - 1]), Math.abs(times[0] - times[times.length - 1])));
        return res;
    }
}

解法2： O(N)

借鉴了bucket sort 的解法，因为这里分钟数的总个数是固定的。可以用一个60 * 24 = 1440的数组来记录每一个分钟数是否出现。
如果一个分钟数出现两次，那么最小值一定是0.
同时需要维护一个first和last来记录第一个和最后一个出现过的分钟数。
最后比较一下相邻出现过的分钟数以及头尾就可以了。
Java

1