【算法】【线性表】【数组】合并区间

news/发布时间2024/4/20 21:09:33

1  题目

以数组 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

2  解答

 

class Solution {public int[][] merge(int[][] intervals) {// 参数边界校验if (intervals == null || intervals.length <= 0) {return intervals;}// 对数组按左坐标进行升序排序Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));// 定义返回结果List<int[]> res = new ArrayList<>();// 根据每个元素的右坐标以及下一个元素的区间进行比较判断逐个遍历for (int i = 0; i < intervals.length; ) {int left = intervals[i][0];int right = intervals[i][1];int j = i + 1;// 如果是最后一个元素了,不需要合并了,直接加入结果结束if (j == intervals.length) {res.add(new int[]{left, right});break;}// 寻找 i 元素可以向后合并的元素for (; j < intervals.length; j++) {int innerLeft = intervals[j][0];int innerRight = intervals[j][1];// 在下一个元素的区间内,然后继续向后遍历if (innerLeft <= right && right <= innerRight) {right = innerRight;continue;}// 包含了下一个区间的也继续向后,比如 [1,4] [2,3]if (right >= innerRight) {continue;}break;}// 说明不在下一个区间了,说明算是一种结果了i = j;res.add(new int[]{left, right});}return res.toArray(new int[res.size()][]); }
}

 

加油。

 

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

如若内容造成侵权/违法违规/事实不符,请联系宁远站长网进行投诉反馈email:xxxxxxxx@qq.com,一经查实,立即删除!

相关文章

ucontext库

目录ucontext接触ucontext到底是什么 ucontext接触 利用ucontext提供的四个函数 getcontext(),setcontext(),makecontext(),swapcontext() 可以在一个进程中实现用户级的线程切换。 #include <unistd.h> #include <ucontext.h> #include <stdio.h>int main()…

免费的虚拟主机还不错

免费的虚拟主机和免费云服务器还不错的阿贝云 https://www.abeiyun.com,

九.流

内容参考: C++文件读写详解(ofstream,ifstream,fstream)_c++ 文件读写-CSDN博客一. 概述 分类: 在程序设计中,用于输入/输出的流是必不可少的。C++中,依照用途不同,流可以被划分位三种:标准IO流:内存与标准输入、输出设备间的通信,一般是控制台。 文件IO流:内存与外…

教职云智慧职教视频课件课程下载工具,如何在电脑端下载智慧职教视频课程课件资料到本地?

一. 安装智慧职教课程下载器 1.获取学无止下载器 https://www.xuewuzhi.cn/icve_downloader 2.下载安装后,然后点击桌面快捷方式运行即可。 注意:杀毒软件可能会阻止外部exe文件运行,并将其当做成病毒,直接添加信任即可,本软件绝对没有木马病毒。 二. 使用说明 1.学无止下…

vulnhub-DC-6

DC-6 是另一个专门建造的易受攻击的实验室,旨在获得渗透测试领域的经验。这不是一个过于困难的挑战,因此对于初学者来说应该很棒。🖳 主机发现 sudo netdiscover -i eth0 -r 192.168.1.0/24Currently scanning: Finished! | Screen View: Unique Hosts …

第二十三天:MYSQL集群Cluster

一、MySQL 主从复制1、主从复制架构和原理 读写分离 复制:每个节点都有相同的数据集,向外扩展,基于二进制日志的单向复制 2、复制架构 (1)一主一从复制架构 (2)一主多从复制架构3、主从复制原理主从复制相关线程 主节点: dump Thread:为每个Slave的I/O Thread启动一个…