LC 539. 最小时间差

题目描述

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

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

示例 1：

输入：timePoints = ["23:59","00:00"]

输出：1

示例 2：

输入：timePoints = ["00:00","23:59","00:00"]

输出：0

提示：

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

---

模拟（排序）

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

因此，一种简单的方式是对于每个 $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(n)$

---

模拟（哈希表计数）

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

然后找到间隔最小两个时间点，这种利用「桶排序」的思路避免了对 $timePoints$ 所对应的偏移量进行排序，而 $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)$

---

最后

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

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

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

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