智能模板网站建设,帮助网站网站做优化,基于python的网站开发项目,常用网站大全题目链接 剑指 Offer II 035. 最小时间差 mid 题目描述
给定一个 24小时制#xff08;小时:分钟 HH:MM#xff09;的时间列表#xff0c;找出列表中任意两个时间的最小时间差并以分钟数表示。
示例 1#xff1a; 输入#xff1a;timePoints [“23:59”,“0…题目链接 剑指 Offer II 035. 最小时间差 mid 题目描述
给定一个 24小时制小时:分钟 HH:MM的时间列表找出列表中任意两个时间的最小时间差并以分钟数表示。
示例 1 输入timePoints [“23:59”,“00:00”] 输出1 示例 2 输入timePoints [“00:00”,“23:59”,“00:00”] 输出0 提示
2timePoints2∗1042 timePoints 2 * 10^42timePoints2∗104timePoints[i]格式为 HH:MM
解法排序
首先我们先将所有的 HH:MM转化为分钟数存入一个列表 time中接着再对它按从小到大排序。
排序之后只可能是相连两个时间点 时间差值最小。还需要考虑首尾相连的时间差值。
时间复杂度 O(n∗logn)O(n * logn)O(n∗logn)
C代码
class Solution {
public:int findMinDifference(vectorstring timePoints) {vectorint 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)))
