[LeetCode] Minimum Time Difference 最短时间差-阿里云开发者社区

开发者社区> 李博 bluemind> 正文

[LeetCode] Minimum Time Difference 最短时间差

简介:
+关注继续查看

Given a list of 24-hour clock time points in "Hour:Minutes" format, find the minimum minutes difference between any two time points in the list.

Example 1:

Input: ["23:59","00:00"]
Output: 1 

Note:

  1. The number of time points in the given list is at least 2 and won't exceed 20000.
  2. The input time is legal and ranges from 00:00 to 23:59. 

这道题给了我们一系列无序的时间点,让我们求最短的两个时间点之间的差值。那么最简单直接的办法就是给数组排序,这样时间点小的就在前面了,然后我们分别把小时和分钟提取出来,计算差值,注意唯一的特殊情况就是第一个和末尾的时间点进行比较,第一个时间点需要加上24小时再做差值,参见代码如下:

解法一:

public:
    int findMinDifference(vector<string>& timePoints) {
        int res = INT_MAX, n = timePoints.size(), diff = 0;
        sort(timePoints.begin(), timePoints.end());
        for (int i = 0; i < n; ++i) {
            string t1 = timePoints[i], t2 = timePoints[(i + 1) % n];
            int h1 = (t1[0] - '0') * 10 + t1[1] - '0';
            int m1 = (t1[3] - '0') * 10 + t1[4] - '0';
            int h2 = (t2[0] - '0') * 10 + t2[1] - '0';
            int m2 = (t2[3] - '0') * 10 + t2[4] - '0';
            diff = (h2 - h1) * 60 + (m2 - m1);
            if (i == n - 1) diff += 24 * 60;
            res = min(res, diff);
        }
        return res;
    }
};

下面这种写法跟上面的大体思路一样,写法上略有不同,是在一开始就把小时和分钟数提取出来并计算总分钟数存入一个新数组,然后再对新数组进行排序,再计算两两之差,最后还是要处理首尾之差,参见代码如下:

解法二:

public:
    int findMinDifference(vector<string>& timePoints) {
        int res = INT_MAX, n = timePoints.size();
        vector<int> nums;
        for (string str : timePoints) {
            int h = stoi(str.substr(0, 2)), m = stoi(str.substr(3));
            nums.push_back(h * 60 + m);
        }
        sort(nums.begin(), nums.end());
        for (int i = 1; i < n; ++i) {
            res = min(res, nums[i] - nums[i - 1]);
        }
        return min(res, 1440 + nums[0] - nums.back());
    }
};

上面两种方法的时间复杂度都是O(nlgn),我们来看一种O(n)时间复杂度的方法,由于时间点并不是无穷多个,而是只有1440个,所以我们建立一个大小为1440的数组来标记某个时间点是否出现过,如果之前已经出现过,说明有两个相同的时间点,直接返回0即可;若没有,将当前时间点标记为出现过。我们还需要一些辅助变量,pre表示之前遍历到的时间点,first表示按顺序排的第一个时间点,last表示按顺序排的最后一个时间点,然后我们再遍历这个mask数组,如果当前时间点出现过,再看如果first不为初始值的话,说明pre已经被更新过了,我们用当前时间点减去pre来更新结果res,然后再分别更新first,last,和pre即可,参见代码如下:

解法三:

public:
    int findMinDifference(vector<string>& timePoints) {
        int res = INT_MAX, pre = 0, first = INT_MAX, last = INT_MIN;
        vector<int> mask(1440, 0);
        for (string str : timePoints) {
            int h = stoi(str.substr(0, 2)), m = stoi(str.substr(3));
            if (mask[h * 60 + m] == 1) return 0;
            mask[h * 60 + m] = 1;
        }
        for (int i = 0; i < 1440; ++i) {
            if (mask[i] == 1) {
                if (first != INT_MAX) {
                    res = min(res, i - pre);
                }
                first = min(first, i);
                last = max(last, i);
                pre = i;
            }
        }
        return min(res, 1440 + first - last);
    }
};

参考资料:

https://discuss.leetcode.com/topic/83250/easy-c-solution

https://discuss.leetcode.com/topic/82573/verbose-java-solution-bucket

https://discuss.leetcode.com/topic/82575/java-o-nlog-n-o-n-time-o-1-space-solutions

本文转自博客园Grandyang,原文链接:[LeetCode] Minimum Time Difference 最短时间差

,如需转载请自行联系原博主。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
LeetCode 380: 常数时间插入、删除和获取随机元素 Insert Delete GetRandom O(1)
题目: 设计一个支持在平均 时间复杂度 O(1) 下,执行以下操作的数据结构。 insert(val):当元素 val 不存在时,向集合中插入该项。 remove(val):元素 val 存在时,从集合中移除该项。
693 0
LeetCode 122 Best Time to Buy and Sell Stock II(股票买入卖出的最佳时间 II)
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50829772 翻译 话说你有一个数组,其中第i个元素表示第i天的股票价格。
654 0
jQuery EasyUI API 中文文档 - 日期时间框(DateTimeBox)
DateTimeBox  日期时间框 扩展自 $.fn.datebox.defaults。用 $.fn.datetimebox.defaults 重写了 defaults。     依赖 datebox timespinner 用法 1.
953 0
jQuery EasyUI API 中文文档 - 时间微调器(TimeSpinner)
TimeSpinner 时间微调器 扩展自 $.fn.spinner.defaults,用 $.fn.timespinner.defaults 重写了 defaults。 依赖 spinner 用法 1. 1. $('#ss').timespinner({   2.     showSeconds:true 3. });  特性 其特性扩展自 spinner,下列是为 timespinner 增加的特性。
736 0
域名年龄对SEO的影响,域名续费时间长短对排名有影响吗?
域名年龄和注册时长在SEO中是否重要? 我在网上看到了一些关于域名年龄和域名续费时长影响搜索排名的意见分歧。许多SEO认为域名年龄和注册时长都会影响搜索引擎排名。我是他们其中的一员。这场辩论已持续多年,因为百度在一轮谈判中表示它不会影响排名。
1114 0
节省时间的那些 Linux 命令
前言:有网友在问答网站Quora上提问:“有哪些省时小技巧,是每个Linux用户都应该知道的?” Joshua Levy 平常就在 Linux 平台工作,并且他积累了不少实用命令行技巧,他在回复中精选出一部分。对技术用户来说,这些技巧挺重要或实用,但知道的人并不多。下文略有点长,一般来说,用户也不需要对全部内容都了解,但为了达到省时方便的目的,Joshua Levy 仍不遗余力做了校对,以保证列出的每一条都值得一读,前提是你是一位Linux重度用户。
42 0
+关注
李博 bluemind
云栖社区Java、Redis、MongoDB运营小编,有意合作请联系钉钉:15810436147
2107
文章
1103
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载