题目描述
这是 LeetCode 上的 539. 最小时间差 ，难度为 中等。
Tag : 「模拟」、「排序」、「哈希表」
给定一个 2424 小时制（小时:分钟 "HH:MM"）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。
示例 1：
输入：timePoints = ["23:59","00:00"] 输出：1 复制代码
示例 2：
输入：timePoints = ["00:00","23:59","00:00"] 输出：0 复制代码
提示：
- 2 <= timePoints <= 2 * 10^42<=timePoints<=2∗104
timePoints[i]格式为"HH:MM"
模拟（排序）
根据题意，我们需要找出「时钟盘」中的夹角最小的两个时间点，其中包括了分布在 00:00 左右两侧（横跨了一天）的时间点。
因此，一种简单的方式是对于每个 timePoints[i]timePoints[i]，我们不仅记录「当天该时间点」对应的的偏移量，还记录「下一天该时间点」对应的偏移量。
处理所有的 timePoints[i]timePoints[i] 后，对偏移量进行排序，遍历找到所有相邻元素之间的最小值。
代码（感谢 @Benhao 和 @🍭可乐可乐吗 同学提供的其他语言版本）：
class Solution { public int findMinDifference(List<String> timePoints) { int n = timePoints.size() * 2; int[] nums = new int[n]; for (int i = 0, idx = 0; i < n / 2; i++, idx += 2) { String[] ss = timePoints.get(i).split(":"); int h = Integer.parseInt(ss[0]), m = Integer.parseInt(ss[1]); nums[idx] = h * 60 + m; nums[idx + 1] = nums[idx] + 1440; } Arrays.sort(nums); int ans = nums[1] - nums[0]; for (int i = 0; i < n - 1; i++) ans = Math.min(ans, nums[i + 1] - nums[i]); return ans; } } 复制代码
class Solution: def findMinDifference(self, timePoints: List[str]) -> int: n = len(timePoints) * 2 nums, idx = [0] * n, 0 for time in timePoints: h, m = int(time[:2]), int(time[-2:]) nums[idx] = h * 60 + m nums[idx + 1] = nums[idx] + 1440 idx += 2 nums.sort() return min(nums[i + 1] - nums[i] for i in range(n - 1)) 复制代码
func findMinDifference(timePoints []string) int { n := len(timePoints) * 2 nums := make([]int, n) for i, idx := 0, 0; i < n / 2; i++ { ss := strings.Split(timePoints[i], ":") h, _ := strconv.Atoi(ss[0]) m, _ := strconv.Atoi(ss[1]) nums[idx] = h * 60 + m nums[idx + 1] = nums[idx] + 1440 idx += 2 } sort.Ints(nums) ans := nums[1] - nums[0]; for i := 1; i < n - 1; i++ { if v := nums[i + 1] - nums[i]; v < ans { ans = v } } return ans } 复制代码
class Solution { public: int findMinDifference(vector<string>& timePoints) { int n = timePoints.size() * 2; vector<int> nums(n); for(int i = 0, idx = 0; i < n / 2; i++, idx += 2){ string ss = timePoints[i]; auto pos = ss.find(':'); int h = stoi(ss.substr(0, pos)), m = stoi(ss.substr(pos + 1)); nums[idx] = h * 60 + m; nums[idx + 1] = nums[idx] + 1440; } sort(nums.begin(), nums.end()); int ans = nums[1] - nums[0]; for(int i = 0; i < n - 1; i++){ ans = min(ans, nums[i + 1] - nums[i]); } return ans; } }; 复制代码
int min(int a,int b){ return a > b ? b : a; } int cmp(const void* a , const void* b){ return (*(int*)a) - (*(int*)b); } int findMinDifference(char ** timePoints, int timePointsSize){ int n = timePointsSize * 2; int* nums = (int*) malloc(sizeof(int) * n); for(int i = 0, idx = 0; i < n / 2; i++, idx += 2){ timePoints[i][2] = '\0'; int h = atoi(timePoints[i]), m = atoi(timePoints[i] + 3); nums[idx] = h * 60 + m; nums[idx + 1] = nums[idx] + 1440; } qsort(nums, n, sizeof(nums[0]), cmp); int ans = nums[1] - nums[0]; for(int i = 0; i < n - 1; i++){ ans = min(ans, nums[i + 1] - nums[i]); } free(nums); nums = NULL; return ans; } 复制代码
- 时间复杂度：O(n\log{n})O(nlogn)
- 空间复杂度：O(n)O(n)
模拟（哈希表计数）
利用当天最多只有 60 * 24 = 144060∗24=1440 个不同的时间点（跨天的话则是双倍），我们可以使用数组充当哈希表进行计数，同时根据「抽屉原理」，若 timePointstimePoints 数量大于 14401440，必然有两个相同时间点，用作剪枝。
然后找到间隔最小两个时间点，这种利用「桶排序」的思路避免了对 timePointstimePoints 所对应的偏移量进行排序，而 O(C)O(C) 的复杂度使得所能处理的数据范围没有上限。
代码：
class Solution { public int findMinDifference(List<String> timePoints) { int n = timePoints.size(); if (n > 1440) return 0; int[] cnts = new int[1440 * 2 + 10]; for (String s : timePoints) { String[] ss = s.split(":"); int h = Integer.parseInt(ss[0]), m = Integer.parseInt(ss[1]); cnts[h * 60 + m]++; cnts[h * 60 + m + 1440]++; } int ans = 1440, last = -1; for (int i = 0; i <= 1440 * 2 && ans != 0; i++) { if (cnts[i] == 0) continue; if (cnts[i] > 1) ans = 0; else if (last != -1) ans = Math.min(ans, i - last); last = i; } return ans; } } 复制代码
- 时间复杂度：O(C)O(C)
- 空间复杂度：O(C)O(C)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.539 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
