LeetCode刷题之HOT100之合并区间

devtools/2024/11/14 6:00:00/

雨下了一整天,中午早早就回去吃饭拿快递了,今天拿了很多快递。我的书回来啦哈哈,还有好多零食,爽歪歪啊,放在下面了,然后准备开始做题啦!
在这里插入图片描述
图一:左一是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/devtools/47168.html

相关文章

流批一体计算引擎-10-[Flink]中的常用算子和DataStream转换

pyflink 处理 kafka数据 1 DataStream API 示例代码 从非空集合中读取数据&#xff0c;并将结果写入本地文件系统。 from pyflink.common.serialization import Encoder from pyflink.common.typeinfo import Types from pyflink.datastream import StreamExecutionEnviron…

QT 信号和槽 多对一关联示例,多个信号,一个槽函数响应,多个信号源如何绑定一个槽函数

三个顾客 Anderson、Bruce、Castiel 都要订饭&#xff0c;分别对应三个按钮&#xff0c;点击一个按钮&#xff0c;就会弹出给该顾客送饭的消息。注意这个例子只使用一个槽函数&#xff0c;而三个顾客名称是不一样的&#xff0c;弹窗时显示的消息不一样&#xff0c;这需要一些 技…

golang协程(go)与信道(chan)使用示例

函数定义 // 普通函数 func f(from string) {//输出三次传入的字符串for i : 0; i < 50; i {fmt.Println(from, ":", i)} } 协程调用 //使用go协程调用函数go f("go routines > Hello World") 局部函数go协程使用 //使用协和调用临时函数go fun…

内存池(Memory Pool)

内存池&#xff08;Memory Pool&#xff09; 内存池&#xff08;Memory Pool&#xff09;是一种内存管理技术&#xff0c;主要用于优化程序中动态内存分配和释放的效率&#xff0c;减少内存碎片&#xff0c;提高程序运行速度。以下是内存池的一些关键概念和工作原理介绍&#…

【AI大模型】Transformers大模型库(七):单机多卡推理之device_map

目录​​​​​​​ 一、引言 二、单机多卡推理之device_map 2.1 概述 2.2 自动配置&#xff0c;如device_map"auto" 2.3 手动配置&#xff0c;如device_map"cuda:1" 三、总结 一、引言 这里的Transformers指的是huggingface开发的大模型库&#x…

Unity 实现WebSocket 简单通信——客户端

创建连接 ClientWebSocket socket new ClientWebSocket(); string url $"ws://{ip}:{port}"; bool createUri Uri.TryCreate(url, UriKind.RelativeOrAbsolute, out Uri uri); if (createUri) {var task socket.ConnectAsync(uri, CancellationToken.None);task…

远程医疗平台如何连接医生和患者?

远程医疗平台&#xff0c;以其创新的信息技术手段&#xff0c;构筑了一个无视地理界限的医疗服务新体系&#xff0c;实现了医患之间的实时互动和诊疗服务。例如欣九康诊疗系统&#xff0c;通过一系列功能模块&#xff0c;有效连接了医生与患者&#xff0c;为两者提供了一个全面…

MFC设置窗口在Z轴上的位置

函数原型&#xff1a; BOOL CWnd::SetWindowPos(const CWnd* pWndInsertAfter, int x, int y, int cx, int cy, UINT nFlags);返回值&#xff1a; 如果函数成功&#xff0c;则返回非零值&#xff1b;否则返回0。 参数&#xff1a; pWndInsertAfter&#xff1a;标识了在Z轴次…