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 \times 10^4$
  • timePoints[i] 格式为 "HH:MM"

模拟（排序）

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

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

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

Java 代码：

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;
    }
}

C++ 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findMinDifference(vector<string>& timePoints) {
        const int n = timePoints.size() * 2;
        vector<int> nums(n);
        for (int i = 0, idx = 0; i < n / 2; i++, idx += 2) {
            int pos = timePoints[i].find(':');
            int h = stoi(timePoints[i].substr(0, pos)), m = stoi(timePoints[i].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;
    }
};

Python 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def findMinDifference(self, timePoints: List[str]) -> int:
        n = len(timePoints) * 2
        nums = [0] * n
        idx = 0
        for t in timePoints:
            h, m = map(int, t.split(':'))
            nums[idx] = h * 60 + m
            nums[idx + 1] = nums[idx] + 1440 
            idx += 2
        nums.sort()
        ans = nums[1] - nums[0]
        for i in range(n - 1):
            ans = min(ans, nums[i + 1] - nums[i])
        return ans

  • 时间复杂度：$O(n\log{n})$
  • 空间复杂度：$O(n)$

模拟（哈希表计数）

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

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

Java 代码：

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;
    }
}

C++ 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int findMinDifference(vector<string>& timePoints) {
        const int n = timePoints.size();
        if (n > 1440) return 0;
        vector<int> cnts(1440 * 2 + 10, 0);
        for (const auto& s : timePoints) {
            size_t colon = s.find(':');
            int h = stoi(s.substr(0, colon)), m = stoi(s.substr(colon + 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) return 0;
            if (last != -1) ans = min(ans, i - last);
            last = i;
        }
        return ans;
    }
};

Python 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def findMinDifference(self, timePoints: List[str]) -> int:
        n = len(timePoints)
        if n > 1440:
            return 0
        cnts = [0] * (1440 * 2 + 10)
        for t in timePoints:
            h, m = map(int, t.split(':'))
            cnts[h * 60 + m] += 1
            cnts[h * 60 + m + 1440] += 1
        ans, last = 1440, -1
        for i in range(1440 * 2 + 1):
            if cnts[i] == 0:
                continue
            if cnts[i] > 1:
                return 0
            if last != -1:
                ans = 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 原题链接和其他优选题解。