剑指 Offer II 035. 最小时间差

题目链接

剑指 Offer II 035. 最小时间差 mid

题目描述

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

示例 1：

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

示例 2：

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

提示：

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

解法：排序

首先我们先将所有的 HH:MM转化为分钟数，存入一个列表 time中，接着再对它按从小到大排序。

排序之后，只可能是相连两个时间点 时间差值最小。（还需要考虑首尾相连的时间差值）。

时间复杂度： $O(n\ast logn)$

C++代码：

class Solution {
public:int findMinDifference(vector<string>& timePoints) {vector<int> time;for(auto s:timePoints){int h = stoi(s.substr(0,2));int m = stoi(s.substr(3,2));time.emplace_back(h * 60 + m);}sort(time.begin(),time.end());int ans = 1e9;int n = time.size();for(int i = 0;i < n - 1;i++){ans = min(ans, time[i + 1] - time[i]);}int d = 24 * 60 - time[n - 1] + time[0];ans = min(ans,d);return ans;}
};

Python代码：

class Solution:def findMinDifference(self, timePoints: List[str]) -> int:time = sorted(int(t[:2]) * 60 + int(t[3:]) for t in timePoints)time.append(time[0] + 24 * 60)return min(time[i] - time[i - 1] for i in range(1, len(time)))