跳到主要内容

539.最小时间差

· 阅读需 5 分钟

1、题干​

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

 

示例 1：

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

示例 2：

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

 

提示：

  • 2 <= timePoints.length <= 2 * 104
  • timePoints[i] 格式为 "HH:MM"

2、解法1-API排序​

前置处理：先排除3种特殊情况

  • 鸽巢原理：timePoints.length > 1440，最小差值为0。因为分钟数最多1440种情况，如果分钟数量超过1440，则必定有重复值。
  • 哈希去重：new Set(timePoints).size < timePoints.length，表示有重复值，最小差值为0。可以只用哈希去重而不用鸽巢原理，这里两个都用一是为省空间，二是为下一个限制条件提前去重。
  • 相邻原理（瞎扯的）：timePoints.length > 720最小差值为1。因为分钟数最多1440种情况，如果分钟数超过一半而没有重复值，则必定有分钟数相邻。

后续步骤：把时间字符串转为分钟数，直接API排序并计算最小差值

  • 将timePoints中的时间字符串HH:MM转成分钟数(0-1400)，构建出新的分钟数数组times
  • 对times进行升序排序
  • 在times数组末尾推入1440+times[0](最小分钟数)，使得最小时间和最大时间的差值计算常规化
  • 对相邻分钟数求差值，最后返回最小差值

3、复杂度​

  • 时间复杂度：O(C)O(C)，其中2<=C<=720∗log7202<=C<=720*log720
  • 空间复杂度：O(C)O(C)

4、代码​

var findMinDifference = function (timePoints) {
    if (timePoints.length > 1440 || new Set(timePoints).size < timePoints.length) return 0;
    if (timePoints.length > 720) return 1;

    const times = timePoints.map(p => 60 * (p[0] + p[1]) + 1 * (p[3] + p[4]));
    times.sort((a, b) => a - b).push(1440 + times[0]);

    return times.reduce((a, c, i) => i ? Math.min(a, c - times[i - 1]) : a, 1440);
};

5、执行结果​

0.png


6、解法2-计数排序​

前置处理：先排除3种特殊情况（同解法1）

  • 鸽巢原理：timePoints.length > 1440，最小差值为0。因为分钟数最多1440种情况，如果分钟数量超过1440，则必定有重复值。
  • 哈希去重：new Set(timePoints).size < timePoints.length，表示有重复值，最小差值为0。可以只用哈希去重而不用鸽巢原理，这里两个都用一是为省空间，二是为下一个限制条件提前去重。
  • 相邻原理（瞎扯的）：timePoints.length > 720最小差值为1。因为分钟数最多1440种情况，如果分钟数超过一半而没有重复值，则必定有分钟数相邻。

后续步骤：把时间字符串转为分钟数，使用计数排序并计算最小差值

  • 创建以分钟数为下标的数组 times，将 timePoints 中的时间字符串HH:MM转成分钟数，对 times 中的分钟数进行计数
  • 对相邻分钟数求差值，计算出最小差值 minDiff
  • 计算最小时间和最大时间的差值，并与上一步的最小值比较，最终结果是：Math.min(minDiff, 1440 + minTime - maxTime);

7、复杂度​

  • 时间复杂度：O(C)O(C)，其中C=1440C=1440
  • 空间复杂度：O(C)O(C)

8、代码​

var findMinDifference = function (timePoints) {
    if (timePoints.length > 1440 || new Set(timePoints).size < timePoints.length) return 0;
    if (timePoints.length > 720) return 1;

    const times = new Array(1440).fill(0);
    for (const p of timePoints) {
        times[60 * (p[0] + p[1]) + 1 * (p[3] + p[4])] += 1;
    }

    let minDiff = 1440, prev = -1440, minTime;
    for (let i = 0; i < times.length; i++) {
        if (minTime === undefined && times[i]) minTime = i;
        if (times[i]) minDiff = Math.min(minDiff, i - prev), prev = i;
    }

    return Math.min(minDiff, 1440 + minTime - prev);
};

9、执行结果​

1.png