面试算法35:最小时间差

这篇具有很好参考价值的文章主要介绍了面试算法35:最小时间差。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

给定一组范围在00:00至23:59的时间,求任意两个时间之间的最小时间差。例如,输入时间数组[“23:50”,“23:59”,“00:00”],"23:59"和"00:00"之间只有1分钟的间隔,是最小的时间差。

分析

这个题目最直观的解法是求出任意两个时间的间隔,然后比较得出最小的时间差。如果输入n个时间,那么需要计算每个时间与另外n-1个时间的间隔,这种蛮力法需要O(n2)的时间。

上述解法的一个优化方法是把n个时间排序。排序之后只需要计算两两相邻的时间之间的间隔,这样就只需要计算O(n)个时间差。由于对n个时间进行排序通常需要O(nlogn)的时间,因此这种优化算法的总体时间复杂度是O(nlogn)。

这里有一个特殊情况值得注意。如果把输入的时间数组[“23:50”,“23:59”,“00:00”]排序,就可以得到[“00:00”,“23:50”,“23:59”]。时间00:00和23:50之间的间隔是1430分钟,而23:50和23:59之间的间隔是9分钟。由于排序之后的第1个时间00:00也可能是第2天的00:00,它和前一天的23:59之间的间隔只有1分钟。也就是说,在计算最小时间差时,需要把排序之后的第1个时间当作第2天的时间(即加上24小时)与最后一个时间之间的间隔也考虑进去。

接着思考如何做进一步优化。前面的算法主要将时间花在排序上面,那么排序是否可以避免?排序是为了计算相邻的两个时间的节点,所以用一个表示时间的数组也可以达到这个目的。

一天有24小时,即1440分钟。如果用一个长度为1440的数组表示一天的时间,那么数组下标为0的位置对应时间00:00,下标为1的位置对应时间00:01,以此类推,下标为1439的位置对应23:59。数组中的每个元素是true或false的标识,表示对应的时间是否存在于输入的时间数组中。

有了这个辅助数组,就只需要从头到尾扫描一遍,相邻的两个为true的值表示对应的两个时间在输入时间数组中是相邻的。例如,输入时间数组[“23:50”,“23:59”,“00:00”],数组中只有下标为0、1430和1439这3个位置的值为true,其他位置的值都是false。

由于数组的下标对应的是时间,因此两个时间之间的时间差就是它们在数组中对应的下标之差。23:50和23:59之间相隔9分钟,它们在数组中的下标之差也是9。文章来源地址https://www.toymoban.com/news/detail-740849.html

public class Test {
    public static void main(String[] args) {
        List<String> timePoints = Arrays.asList("23:50", "23:59", "00:00");
        int result = findMinDifference(timePoints);
        System.out.println(result);
    }

    public static int findMinDifference(List<String> timePoints) {
        if (timePoints.size() > 1440) {
            return 0;
        }

        boolean[] minuteFlags = new boolean[1440];
        for (String time : timePoints) {
            String[] t = time.split(":");
            int min = Integer.parseInt(t[0]) * 60 + Integer.parseInt(t[1]);
            if (minuteFlags[min]) {
                return 0;
            }

            minuteFlags[min] = true;
        }

        return helper(minuteFlags);
    }

    private static int helper(boolean[] minuteFlags) {
        int minDiff = minuteFlags.length - 1;
        int prev = -1;
        int first = minuteFlags.length - 1;
        int last = -1;
        for (int i = 0; i < minuteFlags.length; i++) {
            if (minuteFlags[i]) {
                if (prev >= 0) {
                    minDiff = Math.min(i - prev, minDiff);
                }

                prev = i;
                first = Math.min(i, first);
                last = Math.max(i, last);
            }
        }

        minDiff = Math.min(first + minuteFlags.length - last, minDiff);
        return minDiff;
    }
}

到了这里,关于面试算法35:最小时间差的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Excel如何计算时间差

    =HOUR(B1-A1)\\\"小时 \\\"MINUTE(B1-A1)\\\"分钟 \\\"SECOND(B1-A1)\\\"秒\\\"

    2024年04月23日
    浏览(51)
  • 飞书-多维文档-计算时间差

    如图所示,字段类型选择 公式 单击 公式编辑器 在弹出的公式编辑框中输入公式 TEXT([终结时间]-[开始时间],\\\"HH:MM\\\") [终结时间] 和 [开始时间] 请替换成你的表格中对应的字段名称 HH:MM 表示输出的时间格式为 时:分 其中 “YYY/MM/DD HH:MM” 表示 年月日时分,可以自行选取合适的值

    2024年02月07日
    浏览(67)
  • 解决时间差太大导致Windows无法同步时间

    按微软文档进入注册表修改: HKEY_LOCAL_MACHINESYSTEMCurrentControlSetServicesW32TimeConfig MaxPosPhaseCorrection和MaxNegPhaseCorrection为:0xffffffff (8个F) 但是发现W32TimeConfig里面是空的,而且无法创建 查看config目录权限,发现权限丢失,重新继承权限后修改成功。 另外设置同步时间间隔

    2024年02月16日
    浏览(63)
  • Java计算时间差、日期差

    在java中,计算时间差或日期差有多种方法,以下提供五种示例: 目录 一、使用 Instant 和 Duration 类计算时间差 二、使用 LocalDate 和 ChronoUnit 类计算日期差 三、使用 Joda-Time 库计算时间差和日期差 四、使用 Instant 和 Period 类计算日期差 五、使用 Java 8 的 java.time.tempo

    2024年02月14日
    浏览(46)
  • LocalDate、LocalDateTime计算时间差

    LocalDateTime计算天数和时间差 以下是Jdk1.7存在的问题以及Jdk1.8新特性 Jdk1.7的问题   在Jdk1.8版本发布了新的Date-Time API来加强对时间、日期的处理。这是因为在Jdk1.7中时间、日期的处理上存在如下的一些问题。 非线程安全。Date类是非线程安全的,这是Java时间日期类中最大的

    2023年04月15日
    浏览(36)
  • 【hive 】时间差(天、小时、分、秒)和常用时间格式转

    unix_timestamp()是hive系统时间,格式是timestamp,精确到秒。 unix_timestamp(ymdhms)是把时间转换成timestamp格式,是2018-05-23 07:15:50格式。 unix_timestamp() - unix_timestamp(ymdhms)是两个时间转换为timestamp之后相减,timestamp单位是秒,相减之后是两个时间之间相差的秒数。 CAST((unix_timestamp() - un

    2024年02月03日
    浏览(37)
  • Java计算Date类时间差

    在Java中,我们可以使用Date类来表示日期和时间。如果我们想要计算两个日期之间的时间差,我们可以使用以下步骤: 创建两个Date对象,表示要比较的两个日期。 使用getTime()方法获取每个Date对象的时间戳。 计算两个时间戳之间的差值,以毫秒为单位。 将毫秒转换为所需的

    2024年02月15日
    浏览(40)
  • mysql 日期 计算 时间差 天数差

    第一种:TIMESTAMPDIFF函数 三个参数。第一个参数是比较的类型: FRAC_SECOND、SECOND、 MINUTE、 HOUR、 DAY 、 WEEK 、 MONTH 、 QUARTER、 YEAR 几种类型。第二、三参数是时间, 后减前 : 第二种: DATEDIFF函数 两个参数。前减后。得到相差的天数。 NOW() 当前的年月日时分秒,如:2023-03-09

    2024年02月07日
    浏览(54)
  • 数据存入es 时间差了8个小时

     Mysql  这种现象其实是正常的,因为es默认存储时间的格式是UTC时间,我们一般用的是UTC+8 存入Es后应该是在原来的基础上(UTC+8)-8=UTC 存入到Es后就变成我们看到的样子了 首先知道几个时间名词: (1)GMT:格林威治标准时间 (2)UTC:世界协调时间 (3)DST:夏日节约时间 (

    2024年02月02日
    浏览(36)
  • STM32测相位差(根据时间差)

             两路方波输入到stm32的两路定时器通道,通过检测高电平到来的时间差从而算出相位差, 公式  相位差=360*频率*(时间差)         如果要测正弦波,可以通过电压比较电路转为方波          定时器初始化及定时器中断代码: 在主程序中求其中一路信号的

    2024年02月16日
    浏览(30)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包