LeetCode习题解析-Minimum Time Difference

问题

Given a list of 24-hour clock time points in "Hour:Minutes" format, find the minimum minutes difference between any two time points in the list.

Example 1:

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

Note:

  1. The number of time points in the given list is at least 2 and won't exceed 20000.
  2. The input time is legal and ranges from 00:00 to 23:59.

我的做法

  1. 首先将给出的所有时间都转换成分钟数
  2. 然后转换之后的分钟数容器按照从小到大的顺序排序
  3. 计算相邻之间的时间的分钟数差(最小的一定是相邻的,不可能是离得很远的,这样可以大大减少计算量)
  4. 最后在计算一次头和尾的分钟数差,也就是将头分钟数加上24x60分钟再减去尾分钟数
  5. 保留最小值

可以看出,时间复杂度: O(n),下面给出代码

class Solution:
    def findMinDifference(self, timePoints):
        """
        :type timePoints: List[str]
        :rtype: int
        """
        minutes = [int(time[0:2]) * 60 + int(time[3:5]) for time in timePoints]
        minutes.sort()

        ans = 24 * 60
        for i in range(0, len(minutes) - 1):
            tmp = minutes[i + 1] - minutes[i]
            if tmp < ans:
                ans = tmp
        tmp = minutes[0] + 24 * 60 - minutes[-1]
        if tmp < ans:
            ans = tmp

        return ans