跳到主要内容

剑指 Offer II 035.最小时间差

· 阅读需 4 分钟

1、题干​

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

 

示例 1：

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

示例 2：

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

 

提示：

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

 

注意：本题与主站 539 题相同： https://leetcode-cn.com/problems/minimum-time-difference/

解法1

执行结果​

0.png

解题思路​

前置处理：先排除几种特殊情况：timePoints.length > 1440、timePoints.length > 720、new Set(timePoints).size < timePoints.length。

  • timePoints.length > 1440或new Set(timePoints).size < timePoints.length，则必定有重复值，最小差值为0
  • timePoints.length > 720最小差值为1。因为分钟数最多1440种情况，如果分钟数量超过一半，则必定有分钟数相邻

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

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

整体时间复杂度为O(C)O(C)，其中2<=C<=720∗log7202<=C<=720*log720

代码​

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 => p.split(':').reduce((a, c, i) => a + (+c) * (i ? 1 : 60), 0));
    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);
};

2、解法2​

执行结果​

1.png

解题思路​

前置处理：先排除几种特殊情况：timePoints.length > 1440、timePoints.length > 720、new Set(timePoints).size < timePoints.length。

  • timePoints.length > 1440或new Set(timePoints).size < timePoints.length，则必定有重复值，最小差值为0
  • timePoints.length > 720最小差值为1。因为分钟数最多1440种情况，如果分钟数量超过一半，则必定有分钟数相邻

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

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

整体时间复杂度为O(C)O(C)，其中2<=C<=14402<=C<=1440

代码​

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 (let p of timePoints) {
        times[p.split(':').reduce((a, c, i) => a + (+c) * (i ? 1 : 60), 0)] += 1;
    }

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

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