LeetCode-56. 合并区间【数组 排序】

LeetCode-56. 合并区间【数组 排序】

  • 题目描述:
  • 解题思路一:排序?怎么排?当然是排各个区间的左边界,然后判断下一个边界的左边界与结果数组里面的右边界是否重叠。
  • 解题思路二:优化
  • 解题思路三:0

题目描述:

以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。

示例 1:

输入:intervals = [[1,3],[2,6],[8,10],[15,18]]
输出:[[1,6],[8,10],[15,18]]
解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:

输入:intervals = [[1,4],[4,5]]
输出:[[1,5]]
解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示:

1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104

解题思路一:排序?怎么排?当然是排各个区间的左边界,然后判断下一个边界的左边界与结果数组里面的右边界是否重叠。

python中lambda函数
在这里插入图片描述
在python中实现排序的方式如下:

intervals.sort(key=lambda x: x[0])

实现方式还是有点不同的, 因为在python中的排序函数sort支持直接根据关键字进行排序, 实现起来更加简洁.

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        res = []
        intervals.sort(key = lambda x: x[0])
        res.append(intervals[0])
        for i in range(1, len(intervals)):
            if intervals[i][0] <= res[-1][1]:
                right = max(intervals[i][1], res[-1][1])
                res[-1][1] = right
            else:
                res.append(intervals[i])
        return res

时间复杂度:O(nlogn) 快排
空间复杂度:O(logn)快排栈

解题思路二:优化

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        res = []
        # 空集合直接返回
        intervals.sort(key = lambda x: x[0])
        res.append(intervals[0])
        for i in range(1, len(intervals)):
            if res[-1][1] >= intervals[i][0]:
                res[-1][1] = max(res[-1][1], intervals[i][1])
            else:
                res.append(intervals[i])
        return res 

时间复杂度:O(nlogn) 快排
空间复杂度:O(logn)快排栈

解题思路三:0


时间复杂度:O(n)
空间复杂度:O(n)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/506505.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Linux: 进程优先级

Linux: 进程优先级 一、进程优先级概念二、如何查看进程优先级三、如何修改进程的优先级&#xff08;PRL vs NI&#xff09;四、为何优先级PRL必须限定范围五、进程其他特性 一、进程优先级概念 优先级的本质就是排队&#xff0c;而排队则是资源不足所引起的。在计算机中&#…

《Lost in the Middle: How Language Models Use Long Contexts》AI 解读

作者&#xff1a;明明如月学长&#xff0c; CSDN 博客专家&#xff0c;大厂高级 Java 工程师&#xff0c;《性能优化方法论》作者、《解锁大厂思维&#xff1a;剖析《阿里巴巴Java开发手册》》、《再学经典&#xff1a;《Effective Java》独家解析》专栏作者。 热门文章推荐&am…

【JavaScript 漫游】【049】ES6 规范中对象的扩展

文章简介 本篇文章为【JavaScript 漫游】专栏的第 049 篇文章&#xff0c;对 ES6 规范中对象的扩展知识点进行了记录。具体包括&#xff1a; 属性的简洁表示法属性名表达式方法的 name 属性属性的可枚举性和遍历super 关键字对象的扩展运算符链判断运算符Null 判断运算符新增…

MIT最新研究成果 机器人能够从错误中纠偏 无需编程介入和重复演示

目前科学家们正在努力让机器人变得更加智能&#xff0c;教会他们完成诸如擦拭桌面&#xff0c;端盘子等复杂技能。以往机器人要在非结构化环境执行这样的任务&#xff0c;需要依靠固定编程进行&#xff0c;缺乏场景通用性&#xff0c;而现在机器人的学习过程主要在于模仿&#…

ctf题目

目录 1.文件包含的一道题目&#xff0c;没什么难度&#xff0c; 2.一道sql注入的题目&#xff0c;伪静态 3.限制只能本地访问。 1.文件包含的一道题目&#xff0c;没什么难度&#xff0c; 但是一个点就是它这里去包含的那个文件名就是flag&#xff0c;而不是flag.php也不是f…

Linux之miniconda的安装和使用

一、miniconda简介 Miniconda和Anaconda都是由Continuum Analytics开发的Python发行版。二者的主要区别在于它们所自带的软件包集合的大小。Miniconda是一个免费的conda最低安装程序。它是Anaconda的一个小型引导程序版本&#xff0c;只包括conda、Python、它们都依赖的包&…

C++语言·入门

现在我们讲完了数据结构初阶部分的内容&#xff0c;数据结构剩下的内容会在C语言讲解的差不多的时候加入。 1. 什么是C C语言是结构化模块化的语言&#xff0c;适合处理较小规模的程序。对于复杂的问题&#xff0c;规模较大的程序&#xff0c;需要高度抽象和建模时&#xff0c…

STM32学习笔记(10_1)- I2C通信协议

无人问津也好&#xff0c;技不如人也罢&#xff0c;都应静下心来&#xff0c;去做该做的事。 最近在学STM32&#xff0c;所以也开贴记录一下主要内容&#xff0c;省的过目即忘。视频教程为江科大&#xff08;改名江协科技&#xff09;&#xff0c;网站jiangxiekeji.com 本期开…

Linux基础命令篇之——压缩与解压(tar、gzip、bzip2、zip和unzip)

linux基础命令——解压与压缩 以下是关于Linux命令tar、gzip、bzip2、zip和unzip的详细介绍&#xff1a; 1. tar 这个是Linux用的最多的解压缩命令 tar是Linux系统中用于创建和处理归档文件的命令。归档文件是一个包含多个文件和/或目录的单一文件。常与压缩命令gzip或bzip2结…

【CANN训练营笔记】Atlas 200I DK A2体验手写数字识别模型训练推理

环境介绍 开发板&#xff1a;Huawei Atals 200I DK A2 内存&#xff1a;4G NPU&#xff1a;Ascend 310B4 CANN&#xff1a;7.0 准备环境 下载编译好的torch_npu wget https://obs-9be7.obs.cn-east-2.myhuaweicloud.com/wanzutao/torch_npu-2.1.0rc1-cp39-cp39-linux_aarch…

.NET CORE 分布式事务(四) CAP实现最终一致性

目录 引言&#xff1a; 1.0 最终一致性介绍 2.0 CAP 2.0 架构预览 3.0 .NET CORE 结合CAP实现最终一致性分布式事务 3.1 准备工作(数据库&#xff0c;本文使用的是MySql) 3.1.1 数据模型 3.1.2 DbContext 3.1.3 数据库最终生成 3.2 Nuget引入 3.3 appsettings.json …

【OS探秘】【虚拟化】【软件开发】VirtualBox 虚拟化软件卸载和重装

往期OS系列博文&#xff1a; 【OS探秘】【虚拟化】【软件开发】在Windows 11上安装mac OS虚拟机 【OS探秘】【虚拟化】【软件开发】在Windows 11上安装Kali Linux虚拟机 一、事出有因 近日&#xff0c;笔者的Oracle VM VirtualBox突然抽风了&#xff0c;虚拟机无法启动&…

深入理解MapReduce:从Map到Reduce的工作原理解析

当谈到分布式计算和大数据处理时&#xff0c;MapReduce是一个经典的范例。它是一种编程模型和处理框架&#xff0c;用于在大规模数据集上并行运行计算任务。MapReduce包含三个主要阶段&#xff1a;Map、Shuffle 和 Reduce。 ** Map 阶段 ** Map 阶段是 MapReduce 的第一步&am…

Linux appimage如何正确打开

在之前的文章中&#xff0c;提到使用appimage软件非常方便。 但是首次使用会遇到这样的问题&#xff1a; 1. 双击打不开 2. 在终端打开提示&#xff1a; /home/roy/software/appimage/Obsidian-1.5.11.AppImage dlopen(): error loading libfuse.so.2 AppImages require …

关系型数据库mysql(9)主从复制和读写分离

目录 1. 主从复制和读写分离 2. mysql 支持的复制类型 3.架构图 一.主从复制 1.主从复制的定义 2.主从复制的过程 中继日志&#xff08;Relay Log&#xff09;&#xff1a; 优点&#xff1a; 3.为什么要复制 4.谁复制谁 5.数据放在什么地方 6.主从复制出现的问题 …

基于Uni-app的体育场馆预约系统的设计与实现

文章目录 基于Uni-app的体育场馆预约系统的设计与实现1、前言介绍2、开发技术简介3、系统功能图3、功能实现4、库表设计5、关键代码6、源码获取7、 &#x1f389;写在最后 基于Uni-app的体育场馆预约系统的设计与实现 1、前言介绍 伴随着信息技术与互联网技术的不断发展&#…

服务器固定IP(固定出口IP)去访问外部服务

背景 服务器上有多个IP&#xff0c;那么在服务器请求外部服务的时候&#xff0c;到底是使用哪个IP呢&#xff1f;如果要使用特定的IP去请求外部服务&#xff0c;该如何设置呢&#xff1f; 分析 遇到一个实际的场景&#xff1a; 我们产品和其他产品联调&#xff0c;我们的服务…

软考历史题目

2023.3 1. 磁盘索引块1KB,每个地址项4字节&#xff0c;每个磁盘索引块可以存放256个物理块地址 2.5个地址项为直接索引地址&#xff0c;所以0-5逻辑块是直接索引 3.一级间接地址索引&#xff0c;每个指向的物理块存255个地址 4.二级间接地址&#xff1a;256个间接索引表地址…

Php_Code_challenge16

题目&#xff1a; 答案&#xff1a; 解析&#xff1a; 所以科学计数法绕过即可。

蓝桥杯练习系统(算法训练)ALGO-963 转圈游戏

资源限制 内存限制&#xff1a;128.0MB C/C时间限制&#xff1a;1.0s Java时间限制&#xff1a;3.0s Python时间限制&#xff1a;5.0s 问题描述 n个小伙伴&#xff08;编号从0到n-1&#xff09;围坐一圈玩游戏。按照顺时针方向给n个位置编号&#xff0c;从0到n-1。   …