LC 539. 最小时间差

题目描述

这是 LeetCode 上的 539. 最小时间差 ,难度为 中等

给定一个 $24$ 小时制(小时:分钟 "HH:MM")的时间列表,找出列表中任意两个时间的最小时间差并以分钟数表示。

示例 1:

1
2
3
输入:timePoints = ["23:59","00:00"]

输出:1

示例 2:
1
2
3
输入:timePoints = ["00:00","23:59","00:00"]

输出:0

提示:

  • $2 <= timePoints <= 2 * 10^4$
  • timePoints[i] 格式为 "HH:MM"

模拟(排序)

根据题意,我们需要找出「时钟盘」中的夹角最小的两个时间点,其中包括了分布在 00:00 左右两侧(横跨了一天)的时间点。

因此,一种简单的方式是对于每个 $timePoints[i]$,我们不仅记录「当天该时间点」对应的的偏移量,还记录「下一天该时间点」对应的偏移量。

处理所有的 $timePoints[i]$ 后,对偏移量进行排序,遍历找到所有相邻元素之间的最小值。

代码(感谢 @Benhao@🍭可乐可乐吗 同学提供的其他语言版本):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
}
}

-
1
2
3
4
5
6
7
8
9
10
11
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))

-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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
}

-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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;
}
};

-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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(n)$

模拟(哈希表计数)

利用当天最多只有 $60 * 24 = 1440$ 个不同的时间点(跨天的话则是双倍),我们可以使用数组充当哈希表进行计数,同时根据「抽屉原理」,若 $timePoints$ 数量大于 $1440$,必然有两个相同时间点,用作剪枝。

然后找到间隔最小两个时间点,这种利用「桶排序」的思路避免了对 $timePoints$ 所对应的偏移量进行排序,而 $O(C)$ 的复杂度使得所能处理的数据范围没有上限。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.539 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。