剑指offer

剑指offer035-最小时间差

最小时间差

Posted by 高明 on 2020-01-01

剑指offer035-最小时间差

题目

给定一个 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"

 

注意：本题与主站 539 题相同： https://leetcode-cn.com/problems/minimum-time-difference/

Related Topics
  • 数组
  • 数学
  • 字符串
  • 排序

  • 👍 6
  • 👎 0

    • 思路

    想到还是很好想的

    比如两个时间点 A, B

    0——|——-|——-24
    A B

    因为是环形的，所以A和B的最小值要么是 B-A，要么是 24-B + A-0

    所以我们可以构建数组，以分钟为值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int m = timePoints.size();
    int[] arr = new int[m];

    for (int i = 0; i < m; i++) {
        String t = timePoints.get(i);
        String[] ts = t.split(":");
        int h1 = Integer.valueOf(ts[0]);
        int m1 = Integer.valueOf(ts[1]);
        int hm = h1 * 60 + m1;
        arr[i] = hm;
    }

    0——|——–|——–|———-|———-|———24

    对于数组中的数据，如果遍历，就是取任意两个数据 计算 B-A和 24-B + A-0的最小值

    但是如果先排序，则B-A的最小值只会是相邻之间产生

    24-B + A-0取最小值，则B是最大值，A要是最小值，即首位

    1
    2
    3
    4
    5
    6
    7
    Arrays.sort(arr);
    int res = Integer.MAX_VALUE;
    for (int i = 0; i < m - 1; i++) {
        res = Math.min(arr[i + 1] - arr[i], res);
    }
    res = Math.min(24 * 60 - arr[m - 1] + arr[0], res);
    return res;

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    class Solution {
        public int findMinDifference(List<String> timePoints) {
            if (timePoints.size() < 2) {
                return 0;
            }
            int m = timePoints.size();
            int[] arr = new int[m];

            for (int i = 0; i < m; i++) {
                String t = timePoints.get(i);
                String[] ts = t.split(":");
                int h1 = Integer.valueOf(ts[0]);
                int m1 = Integer.valueOf(ts[1]);
                int hm = h1 * 60 + m1;
                arr[i] = hm;
            }

            Arrays.sort(arr);

            int res = Integer.MAX_VALUE;

            for (int i = 0; i < m - 1; i++) {
                res = Math.min(arr[i + 1] - arr[i], res);
            }
            res = Math.min(24 * 60 - arr[m - 1] + arr[0], res);
            return res;
        }
    }
    FEATURED TAGS
    剑指offer
    FRIENDS