C++中的最小时间差


假设我们有一列24小时制的时间点,格式为“小时:分钟”,我们需要找到列表中任意两个时间点之间的最小分钟差。例如,如果输入为[“12:30”,“15:17”],则返回167。

为了解决这个问题,我们将遵循以下步骤:

  • 定义一个大小为24*60+1的数组ok,初始值都为false。
  • n := tp的大小
  • 对于i从0到n-1
    • hr := 时间的小时部分
    • min := 字符串的分钟部分
    • time := hr * 60 + min
    • 如果ok[time]为true,则返回0,否则将ok[time]设置为true。
  • last := 0, first := inf, ret := inf, prev := -inf
  • 对于i从0到24*60
    • 如果ok[i]为true,则
      • last := i和last的最大值
      • first := i和first的最小值
      • 如果prev不为–inf,则ret := ret和last – prev的最小值
      • prev := i
  • 返回ret和24*60+first-last的最小值。

让我们看看下面的实现来更好地理解;

示例

在线演示

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int findMinDifference(vector<string>& tp) {
      vector <bool> ok(24 * 60 + 1, false);
      int n = tp.size();
      for(int i = 0; i < n; i++){
         int hr = stoi(tp[i].substr(0, 2));
         int min = stoi(tp[i].substr(3, 2));
         int time = hr * 60 + min;
         if(ok[time]) return 0;
         ok[time] = true;
      }
      int last = 0;
      int first = INT_MAX;
      int ret = INT_MAX;
      int prev = INT_MIN;
      for(int i = 0; i <= 24 * 60; i++){
         if(ok[i]){
            last = max(i, last);
            first = min(i, first);
            if(prev != INT_MIN) ret = min(ret, last - prev);
            prev = i;
         }
      }
      return min(ret, 24 * 60 + first - last);
   }
};
main(){
   vector<string> v = {"12:30","15:17"};
   Solution ob;
   cout << (ob.findMinDifference(v));
}

输入

["12:30","15:17"]

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

输出

167

更新于:2020年5月4日

376 次查看

启动你的职业生涯

完成课程获得认证

开始学习
广告