剑指 Offer II 035. 最小时间差

概要

用一个长度为60*24=1440的数组，标记出现的时间点。之后计算两两之间的距离。

题目

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

链接：https://leetcode.cn/problems/569nqc/

思路

时间列表是24小时制，且精确到分。24小时，有1440分钟。

我们可以用一个长度为1440的数组，作为一个哈希表。将每一分钟落到每一个格子里。之后遍历每一个格子，记录有值的格子之间的最短距离。当然，别忘了这一天的最早时间点和最晚时间点之间的时间差，也要参与到计算中。

解法：长度1440的数组记录时间

代码

public int findMinDifference(List<String> timePoints) {
    int[] list = new int[1440];
    for (String timePoint : timePoints) {
        // 有相同的时间点，直接返回0
        int hash = hash(timePoint);
        if (list[hash] == 1) {
            return 0;
        }
        list[hash]++;
    }
    int min = Integer.MAX_VALUE;
    int start = 0;
    int first = 0;
    // 初始化起始节点
    for (int i = 0; i < list.length; i++) {
        if (list[i] != 0) {
            start = i;
            first = i;
            break;
        }
    }

    for (int i = start + 1; i < list.length; i++) {
        if (list[i] > 0) {
            min = Math.min(min, i - start);
            start = i;
        }
    }

    return Math.min(min, list.length - start + first);
}

private int hash(String timePoint) {
    String[] split = timePoint.split(":");
    return Integer.parseInt(split[0]) * 60 + Integer.parseInt(split[1]);

}