Question

剑指 Offer II 035. 最小时间差

题目描述

给定一个 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/problems/minimum-time-difference/

解法

方法一：排序

我们注意到，时间点最多只有 $24 \times 60$ 个，因此，当 $timePoints$ 长度超过 $24 \times 60$，说明有重复的时间点，提前返回 $0$。

接下来，我们首先遍历时间列表，将其转换为“分钟制”列表 $mins$，比如，对于时间点 13:14，将其转换为 $13 \times 60 + 14$。

接着将“分钟制”列表按升序排列，然后将此列表的最小时间 $mins[0]$ 加上 $24 \times 60$ 追加至列表尾部，用于处理最大值、最小值的差值这种特殊情况。

最后遍历“分钟制”列表，找出相邻两个时间的最小值即可。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 为时间点个数。

class Solution:
  def findMinDifference(self, timePoints: List[str]) -> int:
    if len(timePoints) > 24 * 60:
      return 0
    mins = sorted(int(t[:2]) * 60 + int(t[3:]) for t in timePoints)
    mins.append(mins[0] + 24 * 60)
    return min(b - a for a, b in pairwise(mins))

class Solution {
  public int findMinDifference(List<String> timePoints) {
    if (timePoints.size() > 24 * 60) {
      return 0;
    }
    List<Integer> mins = new ArrayList<>();
    for (String t : timePoints) {
      String[] time = t.split(":");
      mins.add(Integer.parseInt(time[0]) * 60 + Integer.parseInt(time[1]));
    }
    Collections.sort(mins);
    mins.add(mins.get(0) + 24 * 60);
    int ans = 1 << 30;
    for (int i = 1; i < mins.size(); ++i) {
      ans = Math.min(ans, mins.get(i) - mins.get(i - 1));
    }
    return ans;
  }
}

class Solution {
public:
  int findMinDifference(vector<string>& timePoints) {
    if (timePoints.size() > 24 * 60) {
      return 0;
    }
    vector<int> mins;
    for (auto& t : timePoints) {
      mins.push_back(stoi(t.substr(0, 2)) * 60 + stoi(t.substr(3)));
    }
    sort(mins.begin(), mins.end());
    mins.push_back(mins[0] + 24 * 60);
    int ans = 1 << 30;
    for (int i = 1; i < mins.size(); ++i) {
      ans = min(ans, mins[i] - mins[i - 1]);
    }
    return ans;
  }
};

func findMinDifference(timePoints []string) int {
  if len(timePoints) > 24*60 {
    return 0
  }
  var mins []int
  for _, t := range timePoints {
    time := strings.Split(t, ":")
    h, _ := strconv.Atoi(time[0])
    m, _ := strconv.Atoi(time[1])
    mins = append(mins, h*60+m)
  }
  sort.Ints(mins)
  mins = append(mins, mins[0]+24*60)
  ans := 1 << 30
  for i, x := range mins[1:] {
    ans = min(ans, x-mins[i])
  }
  return ans
}

function findMinDifference(timePoints: string[]): number {
  if (timePoints.length > 24 * 60) {
    return 0;
  }
  const mins: number[] = timePoints.map(timePoint => {
    const [hour, minute] = timePoint.split(':').map(num => parseInt(num));
    return hour * 60 + minute;
  });
  mins.sort((a, b) => a - b);
  mins.push(mins[0] + 24 * 60);
  let ans = 1 << 30;
  for (let i = 1; i < mins.length; ++i) {
    ans = Math.min(ans, mins[i] - mins[i - 1]);
  }
  return ans;
}