LeetCode 539. 最小时间差

题目

给定一个 24 小时制(小时:分钟 HH:MM)的时间列表,找出列表中任意两个时间的最小时间差并以分钟数表示。

数据范围

2 <= timePoints.length <= 2 * 104
timePoints[i] 格式为 HH:MM

样例

输入 1

timePoints = ["23:59","00:00"]

输出 1

1

输入 2

timePoints = ["00:00","23:59","00:00"]

输出 2

0

关键逻辑

对部分情况提前结束

根据题意,一天只有 24 x 60 = 1440 分钟,即使每分钟一个时间点,那么只要数组长度超过 1440,则必有两个时间点相同,此时可直接判定最小时间差为 0,这就是所谓的鸽巢原理。

排序

目前我使用的是直接对字符串进行排序,也可以先全部转换为分钟数来排序。相对于插入排序,我选择了希尔排序,每次缩小增量为 2,以 LeetCode 为例,插入排序替换为希尔排序可缩短 4ms 的运行时间。

时间比较细节

经排序以后,可直接比较时间差,但是别忘了最小时间差有可能出现在头尾,即 头时间 + 24小时 - 尾时间,此时可先预先比较这个时间并设置为最小时间。

代码

class Solution {
    public int findMinDifference(List timePoints) {
        /*
         * 鸽巢原理,如果时间点数组超过 1440。
         * 由于一天有 24 x 60 = 1440 分钟,因此必有两个相同时间。
         * 此时最小时间必定是 0。
         */
        int length = timePoints.size();
        if (length > 1440) {
            return 0;
        }

        String[] timeArray = timePoints.toArray(new String[0]);

        // 希尔排序
        for (int i = length >> 1; i > 0; i >>= 1) {
            for (int j = i; j < length; j++) {
                int k = j - i;
                String time = timeArray[j];
                for (; k > -1; k -= i) {
                    if (time.compareTo(timeArray[k]) < 0) {
                        timeArray[k + i] = timeArray[k];
                    } else {
                        break;
                    }
                }
                timeArray[k + i] = time;
            }
        }

        // 文本时间转化分钟数
        String[] timeSplit = timeArray[0].split(":");
        int timeMinute = Integer.parseInt(timeSplit[0]) * 60 + Integer.parseInt(timeSplit[1]);
        // 假设最小时间是头时间 + 24 小时(1440 分钟) - 尾时间
        timeSplit = timeArray[length - 1].split(":");
        timeMinute = timeMinute + 1440 - (Integer.parseInt(timeSplit[0]) * 60 + Integer.parseInt(timeSplit[1]));
        int minMinute = timeMinute;

        for (int i = 0; i < length - 1; i++) {
            timeSplit = timeArray[i + 1].split(":");
            timeMinute = Integer.parseInt(timeSplit[0]) * 60 + Integer.parseInt(timeSplit[1]);
            timeSplit = timeArray[i].split(":");
            timeMinute -= Integer.parseInt(timeSplit[0]) * 60 + Integer.parseInt(timeSplit[1]);
            if (timeMinute < minMinute) {
                minMinute = timeMinute;
            }
        }

        return minMinute;
    }
}
此文章是由nikbobo发表在算法分类目录的。将固定链接加入收藏夹。

关于 nikbobo

Nikbobo,本名刘永强,记忆空间站长,男,1998 年出生于广东茂名,至今(2022 年)23 岁,目前(2022 年)就读于广州大学华软软件学院,常以“nikbobo”这个网名混迹互联网。如无特殊注明,Nikbobo 在本站发表的文章,遵循 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议。详情请参阅关于页面的作者介绍。

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注