⏱須臾之間 最小時間差 Minimum Time Difference_Leetcode #539

Henry Be on Unsplash

題目敘述 539. Minimum Time Difference

給定一個輸入陣列timePoints，每個陣列元素都是一個24小時制的時間。

請問最小的時間差距是多少?

註:

請以分鐘為單位回答。

測試範例

Example 1:

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

Example 2:

Input: timePoints = ["00:00","23:59","00:00"]
Output: 0

約束條件

Constraints:

• 2 <= timePoints.length <= 2 * 10^4

輸入陣列timePoints長度介於2~兩萬。

• timePoints[i] is in the format "HH:MM".

示意圖

演算法 Greedy策略 + 排序前處理

先把所有24小時制的timePoint轉成對應的minute分鐘總數。

接著排序所有時間點，從小到大排列。

如上圖所示，最小時間差值 = 相鄰的時間差距最小值。

實作上有一個細節要留意，最早時間-最晚時間的時間差也要一併考慮進去，
算是一個corner case。

60* 24 - timePoints[len(timePoints) - 1] + timePoints[0]

最後回傳最小時間差值作為答案回傳即可。

程式碼 Greedy策略 + 排序前處理

class Solution:
    def toMin(self,time):
        time = time.split(':')
        minutes = (60*int(time[0])) + int(time[1])
        return minutes

    def findMinDifference(self, timePoints: List[str]) -> int:
        
        # HH:MM to corresponding minutes
        for i, time in enumerate(timePoints):
            timePoints[i] = self.toMin(time)

        time_gap = math.inf

        # Sort timestamp in ascending order
        timePoints.sort()

        #calculate the closest time distance of each element except last
        for i in range(0, len(timePoints) - 1): 
            time_gap = min(time_gap, (timePoints[i+1] - timePoints[i]))
        
        # including corner case: 1st timestamp - last timestamp
        time_gap = min(time_gap, 60* 24 - timePoints[len(timePoints) - 1] + timePoints[0]) 
        
        return time_gap

複雜度分析

時間複雜度: O( n log n)

最重的成本落在排序，所需時間為O(n log n)

空間複雜度: O(1)

所用到的皆為固定尺寸臨時變數，所需空間為O(1)常數級別。

Reference

[1] Minimum Time Difference - LeetCode