题目

给定一个 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;
    }
}