LeetCode 539. Minimum Time Difference

原题链接在这里：https://leetcode.com/problems/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.

题解：

利用bucket sort. 把时间转化成的位置标记成true. 若是之前已经标记了说明有duplicate, 可以直接return 0.

从头到尾iterate buckets维护最小diff. 再和首尾相差的diff比较取出最小值.

Time Complexity: O(timePoints.size() + 24*60).

Space: O(24*60).

AC Java:

 1 class Solution {
 2     public int findMinDifference(List<String> timePoints) {
 3         boolean [] mark = new boolean[24*60];
 4         for(String s : timePoints){
 5             String [] parts = s.split(":");
 6             int time = Integer.valueOf(parts[0]) * 60 + Integer.valueOf(parts[1]);
 7             
 8             if(mark[time]){
 9                 return 0;
10             }
11             
12             mark[time] = true;
13         }
14         
15         int res = 24*60;
16         int pre = -1;
17         int first = Integer.MAX_VALUE;
18         int last = Integer.MIN_VALUE;
19         for(int i = 0; i<24*60; i++){
20             if(mark[i]){
21                 if(pre != -1){
22                     res = Math.min(res, i-pre);
23                 }
24                 
25                 pre = i;
26                 first = Math.min(first, i);
27                 last = Math.max(last, i);
28             }
29         }
30         
31         res = Math.min(res, first+24*60-last);
32         return res;
33     }
34 }