排序题目：最小时间差

题目

标题和出处

标题：最小时间差

出处：539. 最小时间差

难度

3 级

题目描述

要求

给定一个 $\text{24}$ 小时制的时间列表，时间以 $\text{"HH:MM"}$ 的形式表示，返回列表中任意两个时间的最小时间差的分钟数表示。

示例

示例 1：

输入：$\text{timePoints = ["23:59","00:00"]}$
输出：$\text{1}$

示例 2：

输入：$\text{timePoints = ["00:00","23:59","00:00"]}$
输出：$\text{0}$

数据范围

• $\text{2}\le \text{timePoints.length}\le \text{2}\times {\text{10}}^{\text{4}}$
• $\text{timePoints[i]}$ 格式为 $\text{"HH:MM"}$

解法

思路和算法

首先将时间列表中的每个时间都转换成分钟数表示，得到分钟数组，则分钟数组的每个元素都在范围 $[0,1439]$ 内。

将分钟数组排序之后，最小时间差一定是数组中的两个相邻时间之差，或者数组的首元素与末元素之差加上 $1440$（一天的分钟数是 $1440$）。遍历排序后的分钟数组中的每一对相邻元素（包括首元素与末元素）计算时间差，即可得到最小时间差。

代码

class Solution {
    public int findMinDifference(List<String> timePoints) {
        int length = timePoints.size();
        int[] timeArr = new int[length];
        for (int i = 0; i < length; i++) {
            String timePoint = timePoints.get(i);
            int hour = Integer.parseInt(timePoint.substring(0, 2));
            int minute = Integer.parseInt(timePoint.substring(3));
            timeArr[i] = hour * 60 + minute;
        }
        Arrays.sort(timeArr);
        int minDifference = timeArr[0] - timeArr[length - 1] + 1440;
        for (int i = 1; i < length; i++) {
            int difference = timeArr[i] - timeArr[i - 1];
            minDifference = Math.min(minDifference, difference);
        }
        return minDifference;
    }
}

复杂度分析

• 时间复杂度：$O(n\log n)$，其中 $n$ 是时间列表 $\text{timePoints}$ 的长度。需要创建长度为 $n$ 的分钟数组并排序，排序需要 $O(n\log n)$ 的时间，排序后遍历数组需要 $O(n)$ 的时间，因此时间复杂度是 $O(n\log n)$。

• 空间复杂度：$O(n)$，其中 $n$ 是时间列表 $\text{timePoints}$ 的长度。需要创建长度为 $n$ 的分钟数组并排序，数组需要 $O(n)$ 的空间，排序需要 $O(\log n)$ 的递归调用栈空间，因此空间复杂度是 $O(n)$。