当前位置: 首页 > news >正文

【数组】Leetcode 57. 插入区间【中等】

插入区间

  • 给你一个 无重叠的 ,按照区间起始端点排序的区间列表 intervals,其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束,并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。

  • 在 intervals 中插入区间 newInterval,使得 intervals 依然按照 starti 升序排列,且区间之间不重叠(如果有必要的话,可以合并区间)。

  • 返回插入之后的 intervals。

注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。

示例 1:

输入:intervals = [[1,3],[6,9]], newInterval = [2,5]
输出:[[1,5],[6,9]]

解题思路

需要将 newInterval 插入到有序且无重叠的区间列表 intervals 中,并且在插入之后仍保持区间的无重叠和有序特性。

  • 1、遍历 intervals,将所有在 newInterval 之前的区间直接加入结果列表 result(在之前的是不会有交集的)。
  • 2、检查是否有需要合并的区间:
  •   如果当前区间与 newInterval 有重叠,则合并它们,更新 newInterval 的起始和结束位置。
    
  •  如果当前区间不再与 newInterval 重叠,说明 newInterval 应该插入在当前位置之前,将 newInterval 加入 result,然后继续将当前及之后的区间加入 result。
    
  • 3、如果遍历完所有区间后 newInterval 仍未被插入,则将 newInterval 加入 result。

Java实现

public class InsertInterval {public int[][] insert(int[][] intervals, int[] newInterval) {List<int[]> result = new ArrayList<>();int i = 0;int n = intervals.length;// 添加所有在 newInterval 之前的区间(没有交集的前半部分)while (i < n && intervals[i][1] < newInterval[0]) {result.add(intervals[i]);i++;}// 合并重叠的区间while (i < n && intervals[i][0] <= newInterval[1]) {//找到最后一个合并的区间newInterval[0] = Math.min(newInterval[0], intervals[i][0]);newInterval[1] = Math.max(newInterval[1], intervals[i][1]);i++;}//加入合并后的区间result.add(newInterval);// 添加newInterval之后的区间(没有交集的后半部分)while (i < n) {result.add(intervals[i]);i++;}return result.toArray(new int[result.size()][]);}public static void main(String[] args) {InsertInterval insertInterval = new InsertInterval();int[][] intervals1 = {{1, 3}, {6, 9}};int[] newInterval1 = {2, 5};int[][] result1 = insertInterval.insert(intervals1, newInterval1);// 输出: [[1, 5], [6, 9]]for (int[] interval : result1) {System.out.println("[" + interval[0] + ", " + interval[1] + "]");}System.out.println("--------------------------------------" );int[][] intervals2 = {{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}};int[] newInterval2 = {4, 9};int[][] result2 = insertInterval.insert(intervals2, newInterval2);// 输出: [[1, 2], [3, 10], [12, 16]]for (int[] interval : result2) {System.out.println("[" + interval[0] + ", " + interval[1] + "]");}}
}

时间空间复杂度

  • 时间复杂度: O(n),其中 n 是区间数组 intervals 的长度。需遍历一次 intervals。
  • 空间复杂度: O(n),用于存储结果列表 result。新数组 result 包含最多 intervals.length + 1 个区间。

相关文章:

  • 【计算机视觉(2)】
  • 【LeetCode算法】第83题:删除排序链表中的重复元素
  • 一文搞透常见的Python编码陷阱(上)(分析+案例)
  • 如何判断一个对象是否已经被回收?
  • C++ 常用UI库
  • 如何消除*** WARNING L16: UNCALLED SEGMENT, IGNORED FOR OVERLAY PROCESS。如何消除函数未使用的警告
  • HTTPS能否避免流量劫持?如何实现HTTPS
  • 正点原子[第二期]Linux之ARM(MX6U)裸机篇学习笔记-24.1,2 SPI驱动实验-SPI协议介绍
  • 【软件测试】bug篇|软件测试的生命周期|描述bug的要素|bug的级别|bug的生命周期|高频面试题:与开发产⽣争执怎么处理
  • SSL VPN
  • C++系列-定位new表达式(placement-new)
  • 一个程序员的牢狱生涯(40)好事
  • 谈谈BlueStore的BitmapAllocator
  • D - New Friends(AtCoder Beginner Contest 350)
  • 海外仓快递系统哪个好?教你快速选到适合自己的管理系统
  • 【从零开始安装kubernetes-1.7.3】2.flannel、docker以及Harbor的配置以及作用
  • HTTP中GET与POST的区别 99%的错误认识
  • javascript数组去重/查找/插入/删除
  • java小心机(3)| 浅析finalize()
  • js 实现textarea输入字数提示
  • js算法-归并排序(merge_sort)
  • Material Design
  • PHP面试之三:MySQL数据库
  • Python_OOP
  • VuePress 静态网站生成
  • Vue--数据传输
  • 基于 Ueditor 的现代化编辑器 Neditor 1.5.4 发布
  • 老板让我十分钟上手nx-admin
  • 前端路由实现-history
  • 如何使用Mybatis第三方插件--PageHelper实现分页操作
  • 小而合理的前端理论:rscss和rsjs
  • 教程:使用iPhone相机和openCV来完成3D重建(第一部分) ...
  • ​LeetCode解法汇总2696. 删除子串后的字符串最小长度
  • ​Linux·i2c驱动架构​
  • ​创新驱动,边缘计算领袖:亚马逊云科技海外服务器服务再进化
  • ######## golang各章节终篇索引 ########
  • #DBA杂记1
  • #stm32整理(一)flash读写
  • (16)Reactor的测试——响应式Spring的道法术器
  • (3)选择元素——(14)接触DOM元素(Accessing DOM elements)
  • (二)fiber的基本认识
  • (求助)用傲游上csdn博客时标签栏和网址栏一直显示袁萌 的头像
  • (数据结构)顺序表的定义
  • (万字长文)Spring的核心知识尽揽其中
  • (转)GCC在C语言中内嵌汇编 asm __volatile__
  • (转)关于多人操作数据的处理策略
  • (自用)learnOpenGL学习总结-高级OpenGL-抗锯齿
  • ***测试-HTTP方法
  • .Net 6.0 处理跨域的方式
  • .net 程序 换成 java,NET程序员如何转行为J2EE之java基础上(9)
  • .NET/C# 使窗口永不激活(No Activate 永不获得焦点)
  • .net开源工作流引擎ccflow表单数据返回值Pop分组模式和表格模式对比
  • .NET平台开源项目速览(15)文档数据库RavenDB-介绍与初体验
  • .Net中ListT 泛型转成DataTable、DataSet
  • /etc/fstab和/etc/mtab的区别