題目

標題和出處

標題：最小時間差

出處：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)$。