给出多个用字符串表示的时间，需要找出时间差的最小值。
先用快速排序对时间进行排序，避免浪费多余时间求不可能的时间差。求出相邻两个时间的时间差，同时比较选出最小值。
#include <iostream>
#include <string>
#include <vector>
using namespace std;void exchange(string &s1, string &s2);
vector<string>::size_type Partition(vector<string> &a, int b, int e);
vector<string>::size_type Rand_Partition(vector<string> &a, int b, int e);
void Quick_Sort(vector<string> &a, int b, int e);
int minus2(string &s1, string& s2);int main(int argc, char** argv)
{vector<string> a = { "09:40","09:10","10: 30" };auto size = a.size();Quick_Sort(a, 0, size - 1);/*for (auto c : a)cout << c << endl;*/int j = size - 1, d = minus2(a[0], a[1]), d1 = 0;for (int i = 1;i < j;++i) {d1 = minus2(a[i], a[i + 1]);if (d > d1) d = d1;}cout << d << endl;system("pause");return 0;
}
void exchange(string &s1, string &s2)
{string s = s1;s1 = s2;s2 = s;
}
//从小到大排序
vector<string>::size_type Partition(vector<string> &a, int b, int e)
{string s = a[e];//用于对比的元素放在最后 int i = b - 1;//区间[i,j]保存的是比对照元素大的元素 for (int j = b;j < e;++j) {if (stoi(a[j]) < stoi(s))exchange(a[j], a[++i]);else if (stoi(a[j]) == stoi(s))if (stoi(a[j].substr(3)) < stoi(s.substr(3)))exchange(a[j], a[++i]);}exchange(a[i + 1], a[e]);//将对照元素放回两个区间中间 return i + 1;
}
//随机选择对照元素
vector<string>::size_type Rand_Partition(vector<string> &a, int b, int e)
{int i = (rand() % (e - b + 1)) + b;//生成在[b,e]的随机数 exchange(a[i], a[e]);return Partition(a, b, e);
}
//快速排序
void Quick_Sort(vector<string> &a, int b, int e)
{if (b < e) {int b1 = Rand_Partition(a, b, e);//被选为对照的元素无序进行比较 Quick_Sort(a, b, b1 - 1);Quick_Sort(a, b1 + 1, e);}
}
//时间减法
int minus2(string &s1, string& s2)
{if (stoi(s1) == stoi(s2))return (stoi(s2.substr(3)) - stoi(s1.substr(3)));else if (stoi(s1) < stoi(s2))return (60 - stoi(s1.substr(3)) + stoi(s2.substr(3)));
}discuss中使用的是STL库中提供的sort排序，利用<limits.h>的最大值INT_MAX赋初值
由于我开始未能考虑到可能出现示例中的情况：假如2个时间不在同一天情况下的时间差更小，所以需要
diff = min(diff, 1440 - diff); class Solution {
public: int findMinDifference(vector<string>& times) { int n = times.size(); sort(times.begin(), times.end()); int mindiff = INT_MAX; for (int i = 0; i < times.size(); i++) { int diff = abs(timeDiff(times[(i - 1 + n) % n], times[i])); diff = min(diff, 1440 - diff); mindiff = min(mindiff, diff); } return mindiff; } private: int timeDiff(string t1, string t2) { int h1 = stoi(t1.substr(0, 2)); int m1 = stoi(t1.substr(3, 2)); int h2 = stoi(t2.substr(0, 2)); int m2 = stoi(t2.substr(3, 2)); return (h2 - h1) * 60 + (m2 - m1); }
};