从Leetcode 每日一题练习继续讨论：
539. 最小时间差
539. Minimum Time Difference
题解
本题要求列表中任意两个时间之间的最短时间差, 注意仅要求求出时间差, 不要求给出是具体哪两个时间对应的时间差, 也不要求给出时间的具体位置. 则通过给时间排序, 再遍历排好序的时间数组找到相邻有序时间之间差值的最小值. 排序可以先将时间全部转换为从0点开始的分钟数再给分钟数排序, 这样排序时只需对整数排序, 也方便计算时间差值.
在排序时从0点开始排序, 24点为最大值, 则在计算时间之间的差值时最后还要计算一下最后一个时间和第一个时间反向的差值(排序是顺时针的, 这里相当于计算下逆时针的时间差, 因为时间相当于一个圆形)与最小差值比较并更新. 注意以上针对的均为所有时间都不相同的情况, 若存在两个时间相同, 直接返回0.
c++中的set 标准库表示的有序集合是内部自动有序且不含重复元素的容器, 因此可以利用这个数据结构来保存给出的时间转换后的分钟数.
代码
class Solution {
public:
int findMinDifference(vector<string>& timePoints) {
set<int> minutesSet;
for (const auto& timePoint : timePoints){
int hours = stoi(timePoint.substr(0, 2));
int minute = stoi(timePoint.substr(3, 2));
int minutes = hours*60 + minute;
if (minutesSet.contains(minutes)){
return 0;
}
minutesSet.insert(minutes);
}
int last = 0;
int mintime = 1441;
set<int>::iterator first = minutesSet.begin();
set<int>::iterator it = minutesSet.begin();
last = *it;
it++;
while (it != minutesSet.end()){
mintime = min(mintime, *it-last);
last = *it;
it++;
}
mintime = min(mintime, *first+1440-last);
return mintime;
}
};