LeetCode539.最小时间差：「字符串排序」&「桶排序：哈希计数」

浏览次数 : 次 2022-01-18

博文字数统计 : 1.4k字 | 阅读所需时长 : 6分

× 文章目录

1. LeetCode539.最小时间差：「字符串排序」&「桶排序：哈希计数」

LeetCode539：最小时间差
- 时间：2022-01-18
- 力扣难度：Medium
- 个人难度：Medium-
- 数据结构：数组、时间
- 算法：桶排序、哈希计数、鸽巢原理

LeetCode539.最小时间差：「字符串排序」&「桶排序：哈希计数」

1. 题目描述

题目：原题链接
- 给定一个 24 小时制（小时:分钟 “HH:MM”）的时间列表
- 找出列表中任意两个时间的最小时间差并以分钟数表示。
- 2 <= timePoints <= 2 * 104
- timePoints[i] 格式为 “HH:MM”
输入输出规范
- 输入：时间数组
- 输出：最小的时间差，以分钟表示
输入输出示例
- 输入：timePoints = [“00:00”,”23:59”,”00:00”]
- 输出：0

2. 方法一：排序

思路
- 本题要求出时间数组中的两个元素间的最小差，最容易想到的是直接暴力两重遍历来解决，复杂度为平方级，这里就不进行展示
- 其实，如果可以先将数组进行排序，那么排序后只需要遍历一次数组，在相邻元素的差值中找到最小值即可，复杂度依赖于排序的复杂度，一般降低到线性对数级
- 由于时间数组中的元素是字符串，格式为 “HH:MM”，所以排序的时候需要一些特殊处理
  - 方式一：将时间字符串转化为整型时间，单位为分钟，即hour*60+minute，然后直接排序即可，除了排序还需要额外的 $O(n)$ 空间
  - 方式二：直接对时间字符串进行排序，排序后在遍历的时候在将其转化为时间，除了排序外无需额外的空间
- 最后，因为对于00:mm和23:xx形式的时间，同样需要纳入计算，此时排序后如果存在这种情况，就需要计算首尾元素的差值并比较

题解：字符串排序

// 1. 对时间字符串排序
public int findMinDifference(List<String> timePoints) {
    if (timePoints == null || timePoints.size() == 0) return 0;
    int n = timePoints.size();
    Collections.sort(timePoints);
    int minDiff = Integer.MAX_VALUE;
    for (int i = 1; i < n; i++) {
        minDiff = Math.min(minDiff, getMinute(timePoints.get(i)) - getMinute(timePoints.get(i - 1)));
    }
    // 首尾元素
    int firstTime = getMinute(timePoints.get(0));
    int lastTime = getMinute(timePoints.get(n - 1));
    minDiff = Math.min(minDiff, firstTime - lastTime + 1440);
    return minDiff;
}

private int getMinute(String timeString) {
    String[] time = timeString.split(":");
    return Integer.parseInt(time[0]) * 60 + Integer.parseInt(time[1]);
}

复杂度分析：n 是输入的数组的大小
- 时间复杂度：$O(nlogn)$，调用的排序API是优化的快排，线性对数级复杂度
- 空间复杂度：$O(logn)$，排序时需要的栈空间

3. 方法二：桶排序 & 哈希计数 & 鸽巢原理

思路
- 首先，引入一个很简单的定理：鸽巢原理，该原理描述的是一定的鸽子数量分到一定数量的鸽巢中，当鸽子数量大于鸽巢数量时，必然会有鸽子分配在一起，也称为抽屉原理
- 根据鸽巢原理，我们计算一天的分钟数为24*60=1440分钟，即当时间数组的长度大于1440时，必然有重复的时间，时间差一定为0，可以通过该原理进行剪枝，这就将长度大于1440时复杂度优化到常量级
- 另外，对于长度小于1440的情况，我们也可以维护一个长度为1440的数组(Map自然也可以)作为哈希表来进行计数，这种思想和桶排序的思想是非常一致的，即将一天的时间看作1440个bucket
- 哈希计数完成后，直接遍历该长度确定(1440)的数组，如果存在一个bucket中有多个元素，说明时间重复，直接返回0，两个bucket都只有一个元素，则两者的差值为两者的索引之差

题解：桶排序思想：哈希计数

// 2. 桶排序 & 哈希计数
public int findMinDifference(List<String> timePoints) {
    if (timePoints == null || timePoints.size() == 0) return 0;
    int n = timePoints.size();
    if (n > 1440) return 0;
    int[] bucket = new int[1440];
    for (String timePoint : timePoints) {
        bucket[getMinute(timePoint)]++;
    }
    int minDiff = Integer.MAX_VALUE;
    int first = 0, last = -1;
    for (int i = 0; i < bucket.length; i++) {
        if (bucket[i] > 1) return 0;
        if (bucket[i] == 0) continue;
        if (last != -1) {
            minDiff = Math.min(minDiff, i - last);
        }else {
            first = i; // 首个bucket中只有一个元素
        }
        last = i; // 当前bucket中只有一个元素，遍历结束时就是最后一个只有一个元素的bucket
    }
    // 首尾元素
    minDiff = Math.min(minDiff, first - last + 1440);
    return minDiff;
}

private int getMinute(String timeString) {
    String[] time = timeString.split(":");
    return Integer.parseInt(time[0]) * 60 + Integer.parseInt(time[1]);
}

复杂度分析：n 是输入的数组的大小
- 时间复杂度：$O(n)$，哈希计数需要线性复杂度，遍历哈希表需要常量级，C = 1440
- 空间复杂度：$O(C)$，只使用了bucket数组的额外空间，常量级，C = 1440
优化
- 可以在哈希计数的时候就进行剪枝
- 剪枝条件：判断当前bucket中的元素个数，大于等于1直接return 0，否则才计数

题解：剪枝优化

// 2. 桶排序 & 哈希计数
public int findMinDifference(List<String> timePoints) {
    if (timePoints == null || timePoints.size() == 0) return 0;
    int n = timePoints.size();
    if (n > 1440) return 0;
    int[] bucket = new int[1440];
    for (String timePoint : timePoints) {
        if (bucket[getMinute(timePoint)] >= 1) return 0;
        bucket[getMinute(timePoint)]++;
    }
    int minDiff = Integer.MAX_VALUE;
    int first = 0, last = -1;
    for (int i = 0; i < bucket.length; i++) {
        if (bucket[i] > 1) return 0;
        if (bucket[i] == 0) continue;
        if (last != -1) {
            minDiff = Math.min(minDiff, i - last);
        }else {
            first = i; // 首个bucket中只有一个元素
        }
        last = i; // 当前bucket中只有一个元素，遍历结束时就是最后一个只有一个元素的bucket
    }
    // 首尾元素
    minDiff = Math.min(minDiff, first - last + 1440);
    return minDiff;
}

private int getMinute(String timeString) {
    String[] time = timeString.split(":");
    return Integer.parseInt(time[0]) * 60 + Integer.parseInt(time[1]);
}

本文作者： Chthollists
发布时间： 2022-01-18 14:24:36
最后更新： 2022-01-21 23:09:05
本文标题： LeetCode539.最小时间差：「字符串排序」&「桶排序：哈希计数」
本文链接： https://chthollists.github.io/post/ba1b0ff0.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！