LeetCode刷题之HOT100之合并区间

news/2024/9/24 0:29:48/

雨下了一整天,中午早早就回去吃饭拿快递了,今天拿了很多快递。我的书回来啦哈哈,还有好多零食,爽歪歪啊,放在下面了,然后准备开始做题啦!
在这里插入图片描述
图一:左一是xh送我的,非常精彩(其他都是618购入)只买了陀爷和小波的,白夜行是朋友极力推荐购入
下次购书就不知道是啥时候了,毕竟现在任务落在我们身上,很难挤出时间来看看。Anyway,随性些,做题吧!

1、题目描述

在这里插入图片描述

2、逻辑分析

题目要求很清晰。我的大致思路是:遍历每个数组,将 i + 1个数组的第一个元素a与第 i 个数组的第二个元素b进行比较,如果a < b , 那么这两个数组满足要求,需要合并。如 [1,3] , [2,6]。2 < 3,亟需合并。是的,我写不出来。看了题解发现我想的太easy,很多情况未考虑。题解思路:

  1. 先排序,将整个数组以第一个元素进行排序。
  2. 遍历区间,如果结果数组是空的,或者当前区间的起始位置 >
    结果数组中最后区间的终止位置,则不合并,直接将当前区间加入结果数组。反之将当前区间合并至结果数组的最后区间。

3、代码演示

public int[][] merge(int[][] intervals) {// 第一步:根据区间的起始值对数组进行排序  // 使用lambda表达式定义排序规则,按照每个区间的第一个元素(即起始值)进行升序排序Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);// 第二步:初始化结果数组,大小与原始区间数组相同(但可能不完全使用)int [][] res = new int[intervals.length][2];// index用于跟踪结果数组中当前已使用的最后一个位置int index = -1;// 第三步:遍历排序后的区间数组for(int [] interval : intervals){// 如果结果数组为空,或者当前区间的起始值大于结果数组中最后一个区间的结束值  // 则说明当前区间与前一个区间没有重叠,可以直接添加到结果数组中if(index == -1 || interval[0] > res[index][1]){// 注意这里++index是先使用index的值,再自增res[++index] = interval;}else{// 如果当前区间与前一个区间有重叠  // 则更新结果数组中最后一个区间的结束值为当前区间和前一个区间的结束值中的较大者  // 这样可以确保合并后的区间包含所有重叠的部分  res[index][1] = Math.max(res[index][1], interval[1]);}}// 第四步:返回合并后的区间数组  // 因为结果数组可能并没有完全使用,所以需要复制一个只包含有效区间的新数组  // Arrays.copyOf方法用于创建一个新数组,并复制指定长度的元素到新数组中return Arrays.copyOf(res, index + 1);// index + 1表示有效区间的数量}

这注释解释的较明了,一看就会,一做就废,还在新手期,加油吧!hx。
在这里插入图片描述

4、复杂度分析

时间复杂度: O ( n log ⁡ n ) O(n\log n) O(nlogn)。其中 n 为区间的数量。除去排序的开销,我们只需要一次线性扫描,所以主要的时间开销是排序的 O ( n log ⁡ n ) O(n\log n) O(nlogn)
空间复杂度: O ( log ⁡ n ) O(\log n) O(logn)。其中 n 为区间的数量。这里计算的是存储答案之外,使用的额外空间。 O ( log ⁡ n ) O(\log n) O(logn) 即为排序所需要的空间复杂度。

over,拜拜~


http://www.ppmy.cn/news/1468826.html

相关文章

文件IOoooo

1.1 文件路径 文件路径分为两种&#xff1a; 1、绝对路径&#xff1a;以C:、D:等盘符开头的&#xff0c;就是我们所说的绝对路径&#xff0c;根据它可以直接找到文件的具体位置。 2、相对路径&#xff1a;需要先指定一个目录作为基准目录&#xff0c;从基准目录出发&#xf…

GWT 与 Python App Engine 集成

将 Google Web Toolkit (GWT) 与 Python App Engine 集成可以实现强大的 Web 应用程序开发。这种集成允许你使用 GWT 的 Java 客户端技术构建丰富的用户界面&#xff0c;并将其与 Python 后端结合在一起&#xff0c;后端可以运行在 Google App Engine 上。 1、问题背景 在 Pyt…

代码随想录算法训练营第36期DAY48

感觉要没书读了。。 DAY48 卡码网57爬楼梯 复习一遍&#xff1a;背包容量在外层循环&#xff0c;物品在内层循环&#xff0c;则为排序数&#xff1b; 物品在外层循环&#xff0c;背包容量在内层循环&#xff0c;则为组合数。 #include<iostream>#include<vector&…

泰昆集团分享:新疆泰昆农牧产业数字化建设规划

下文为新疆泰昆集团CIO卢建刚的演讲全文&#xff1a; 大家好&#xff0c;我是新疆泰昆集团有限责任公司的信息总监。新疆泰昆发展将近30年了&#xff0c;是一个全国型的农牧企业。从1996年开始&#xff0c;我们专注农业版块。整个布局前期基本上在新疆发展&#xff0c;2019年战…

【Matlab 六自由度机器人】Fixed Angles(固定角度) 和 Euler Angles(欧拉角) 之间的区别

【Matlab 六自由度机器人】Fixed Angles&#xff08;固定角度&#xff09; 和 Euler Angles&#xff08;欧拉角&#xff09; 之间的区别 往期回顾前言正文Fixed Angles (固定角度)基本概念数学表示MATLAB代码示例 Euler Angles (欧拉角)基本概念数学表示MATLAB代码示例 MATLAB代…

渗透测试之内核安全系列课程:Rootkit技术初探(三)

今天&#xff0c;我们来讲一下内核安全&#xff01; 本文章仅提供学习&#xff0c;切勿将其用于不法手段&#xff01; 目前&#xff0c;在渗透测试领域&#xff0c;主要分为了两个发展方向&#xff0c;分别为Web攻防领域和PWN&#xff08;二进制安全&#xff09;攻防领域。在…

30岁迷茫?AI赛道,人生新起点

前言 30岁&#xff0c;对于许多人来说&#xff0c;是一个人生的分水岭。在这个年纪&#xff0c;有些人可能已经在某个领域取得了不小的成就&#xff0c;而有些人则可能开始对未来的职业方向感到迷茫。如果你正处于这个阶段&#xff0c;那么你可能会问自己&#xff1a;30岁转行…

ES6中的class类 及 递归

es6 中的 class可以把它看成是 es5 中构造函数的语法糖&#xff0c;它简化了构造函数的写法&#xff0c;类的共有属性放到 constructor 里面 1. 通过 class 关键字创建类&#xff0c;类名需要定义首字母大写 2.类里面有个 constructor 函数&#xff0c;可以接受传递过来的参数…