↓ 跳过正文
曙光磁铁的小站

18日 No.539 最小时间差

·614 字·2 分钟
曙光磁铁
作者
曙光磁铁

原贴地址：https://dawnmagnet.github.io/algorithm-station/docs/2022/1/18

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-time-difference
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路分析
#

首先使用一个函数将日期转化成指定分钟的数字，然后将这个数字对应到一个1440(24*60)长度的布尔数组中，然后去枚举布尔数组哪里有值。本来也可以使用一个数组去排序，但数据量太小了(1440)，排序也没什么必要。

放到数组里面之后，因为有两种可能，一种是两个有效值之间的间隔，一种是第一个值和最后一个值的间隔。所以在判断的时候需要多加注意

Rust代码
# 

pub fn parse(s: &str) -> usize {
    let mut res = 0;
    let b: Vec<usize> = s.as_bytes().iter().map(|&x| x as usize - 48).collect();
    (b[0] * 10 + b[1]) * 60 + b[3] * 10 + b[4]
}
impl Solution {
    pub fn find_min_difference(time_points: Vec<String>) -> i32 {
        let mut c = [false; 1440];
        for item in &time_points {
            let pos = parse(item);
            if c[pos] {
                return 0; 
            } else {
                c[parse(item)] = true;
            }
        }
        let mut cur = usize::MAX;
        let mut res = 10000;
        let mut first = 0;
        for time in 0..1440 {
            if c[time] {
                if cur == usize::MAX {
                    cur = time;
                    first = time + 1440;
                } else {
                    res = res.min(time - cur);
                    cur = time;
                }
            }
        }
        res = res.min(first - cur);
        res as i32
    }
}