原文链接: https://leetcode-cn.com/problems/minimum-time-difference

英文原文

Given a list of 24-hour clock time points in "HH:MM" format, return the minimum minutes difference between any two time-points in the list.

 

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 <= 2 * 104
• timePoints[i] is in the format "HH:MM".

中文题目

给定一个 24 小时制（小时:分钟 "HH:MM"）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。

 

示例 1：

输入：timePoints = ["23:59","00:00"]
输出：1

示例 2：

输入：timePoints = ["00:00","23:59","00:00"]
输出：0

 

提示：

• 2 <= timePoints <= 2 * 104
• timePoints[i] 格式为 "HH:MM"

通过代码

高赞题解

由于分钟数最多为24*60，若时间点个数超过24*60，则必有重复，最小时间差为0.

方法1：排序求解

解题思路

先将每个时间转换为分钟数，并排序，然后从头开始遍历，比较相邻两个时间差值，最后在比较首尾两个时间差值。
注意：不要忘记比较首尾时间

代码

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

方法2：哈希求解

解题思路

将所有时间点转化为分钟数，由于分钟数最多为24*60，所以我们将其映射到一个大小为1440的数组中进行求解，数组中存储 该位置索引对应的分钟数 所出现的次数，若存在大于1的情况，则最小时间差必为0。之后，按照顺序求解相邻分钟数的最小差值即可，注意不要忘记比较首尾时间（1440-last+first）。

代码

class Solution {
    public int findMinDifference(List<String> timePoints) {
        if(timePoints.size() > 1440){
            return 0;
        }
        int[] ishas = new int[1440];
        for(int i = 0; i < timePoints.size(); i++){
            String timeStr = timePoints.get(i);
            int time = Integer.parseInt(timeStr.substring(0, 2)) * 60 + Integer.parseInt(timeStr.substring(3));
            if(ishas[time] >= 1)
                return 0;
            ishas[time]++;
        }
        int mindiff = 1440, pre = -1, first = -1;
        for(int i = 0; i < ishas.length; i++){
            if(ishas[i] == 1){
                if(pre != -1)
                    mindiff = Math.min(mindiff, i - pre);
                else
                    first = i;
                pre = i;
            }
        }
        mindiff = Math.min(mindiff, 1440 - pre + first);
        return mindiff;
    }
}

统计信息

通过次数	提交次数	AC比率
15196	25314	60.0%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言