首页 > 其他分享 >力扣第五十七题——插入区间

力扣第五十七题——插入区间

时间:2024-08-12 09:25:35浏览次数:15  
标签:tmp returnSize int 力扣 插入 intervals 第五十七 数组 区间

内容介绍

给你一个 无重叠的 ,按照区间起始端点排序的区间列表 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]]

示例 2:

输入:intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出:[[1,2],[3,10],[12,16]]
解释:这是因为新的区间 [4,8][3,5],[6,7],[8,10] 重叠。

提示:

  • 0 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 105
  • intervals 根据 starti 按 升序 排列
  • newInterval.length == 2
  • 0 <= start <= end <= 105

完整代码

 int** insert(int** intervals, int intervalsSize, int* intervalsColSize, int* newInterval, int newIntervalSize, int* returnSize, int** returnColumnSizes) {
    *returnSize = 0;
    int left = newInterval[0];
    int right = newInterval[1];
    bool placed = false;
    int** ans = malloc(sizeof(int*) * (intervalsSize + 1));
    *returnColumnSizes = malloc(sizeof(int*) * (intervalsSize + 1));
    for (int i = 0; i < intervalsSize; ++i) {
        int* interval = intervals[i];
        if (interval[0] > right) {
            // 在插入区间的右侧且无交集
            if (!placed) {
                int* tmp = malloc(sizeof(int) * 2);
                tmp[0] = left, tmp[1] = right;
                (*returnColumnSizes)[*returnSize] = 2;
                ans[(*returnSize)++] = tmp;
                placed = true;
            }
            int* tmp = malloc(sizeof(int) * 2);
            memcpy(tmp, interval, sizeof(int) * 2);
            (*returnColumnSizes)[*returnSize] = 2;
            ans[(*returnSize)++] = tmp;
        } else if (interval[1] < left) {
            // 在插入区间的左侧且无交集
            int* tmp = malloc(sizeof(int) * 2);
            memcpy(tmp, interval, sizeof(int) * 2);
            (*returnColumnSizes)[*returnSize] = 2;
            ans[(*returnSize)++] = tmp;
        } else {
            // 与插入区间有交集,计算它们的并集
            left = fmin(left, interval[0]);
            right = fmax(right, interval[1]);
        }
    }
    if (!placed) {
        int* tmp = malloc(sizeof(int) * 2);
        tmp[0] = left, tmp[1] = right;
        (*returnColumnSizes)[*returnSize] = 2;
        ans[(*returnSize)++] = tmp;
    }
    return ans;
}

思路详解

一、问题背景

给定一个二维数组intervals,其中每个子数组表示一个区间,我们需要合并这些区间,使得没有重叠的区间尽可能紧密相连。同时,我们有一个新的区间newInterval,需要将其插入到intervals中。

二、解题思路

  1. 排序

    • 首先,我们需要对intervals数组进行排序。排序的依据是每个子数组的第一个元素,因为合并的目的是让没有重叠的区间尽可能紧密相连。
  2. 插入新区间

    • 创建一个List<int[]>,用于存储合并后的区间。
    • 遍历排序后的intervals数组,对于每个区间,根据合并策略添加或更新列表中的区间。
    • 同时,插入新区间newInterval,根据新区间与当前区间的相对位置,决定是否需要更新列表中的区间。
  3. 返回结果

    • 遍历完成后,将List<int[]>转换为二维数组并返回。

三、代码详解

  1. 排序
    • 使用Arrays.sort方法对intervals数组进行排序,比较器比较的是每个子数组的第一个元素。
Arrays.sort(intervals, new Comparator<int[]>() {
    public int compare(int[] interval1, int[] interval2) {
        return interval1[0] - interval2[0];
    }
});
  1. 插入新区间
    • 遍历排序后的intervals数组,对于每个区间,根据合并策略添加或更新列表中的区间。
    • 同时,插入新区间newInterval,根据新区间与当前区间的相对位置,决定是否需要更新列表中的区间。
for (int i = 0; i < intervalsSize; ++i) {
    int* interval = intervals[i];
    if (interval[0] > right) {
        // 在插入区间的右侧且无交集
        if (!placed) {
            int* tmp = malloc(sizeof(int) * 2);
            tmp[0] = left, tmp[1] = right;
            (*returnColumnSizes)[*returnSize] = 2;
            ans[(*returnSize)++] = tmp;
            placed = true;
        }
        int* tmp = malloc(sizeof(int) * 2);
        memcpy(tmp, interval, sizeof(int) * 2);
        (*returnColumnSizes)[*returnSize] = 2;
        ans[(*returnSize)++] = tmp;
    } else if (interval[1] < left) {
        // 在插入区间的左侧且无交集
        int* tmp = malloc(sizeof(int) * 2);
        memcpy(tmp, interval, sizeof(int) * 2);
        (*returnColumnSizes)[*returnSize] = 2;
        ans[(*returnSize)++] = tmp;
    } else {
        // 与插入区间有交集,计算它们的并集
        left = fmin(left, interval[0]);
        right = fmax(right, interval[1]);
    }
}
  1. 返回结果
    • 遍历完成后,将List<int[]>转换为二维数组并返回。
return ans;

四、总结

通过上述步骤,我们能够有效地合并区间,并将新区间插入到区间列表中。关键在于正确地排序区间并合并它们。这种方法的时间复杂度为O(n log n),其中n是intervals数组的长度,因为排序操作的时间复杂度为O(n log n)。空间复杂度为O(n),用于存储合并后的区间。

知识点精炼

一、核心概念

  1. 排序算法:在解决组合问题时,排序可以帮助我们找到最优解或近似解。
  2. 动态规划:在某些情况下,我们可以通过动态规划来优化算法,减少重复计算。
  3. 二维数组:在处理与位置相关的数据时,二维数组是一个非常有用的数据结构。

二、知识点精炼

  1. 区间合并问题

    • 给定一个二维数组intervals,其中每个子数组表示一个区间,需要合并这些区间,使得没有重叠的区间尽可能紧密相连。
  2. 插入新区间

    • 创建一个List<int[]>,用于存储合并后的区间。
    • 遍历排序后的intervals数组,对于每个区间,根据合并策略添加或更新列表中的区间。
    • 同时,插入新区间newInterval,根据新区间与当前区间的相对位置,决定是否需要更新列表中的区间。
  3. 返回结果

    • 遍历完成后,将List<int[]>转换为二维数组并返回。

三、性能分析

  • 时间复杂度:O(n log n),其中n是intervals数组的长度,因为排序操作的时间复杂度为O(n log n)。
  • 空间复杂度:O(n),用于存储合并后的区间。

四、实际应用

  • 数据处理:在处理与位置相关的数据时,这种算法可以帮助我们合并区间,使得没有重叠的区间尽可能紧密相连。
  • 算法竞赛:在算法竞赛中,掌握这种算法对于解决与区间合并相关的问题非常有帮助。

五、代码实现要点

  • 排序:正确使用Arrays.sort方法进行排序。
  • 合并区间:正确实现合并策略,避免数组越界和重复添加。
  • 返回结果:正确返回合并后的区间数组。

 

标签:tmp,returnSize,int,力扣,插入,intervals,第五十七,数组,区间
From: https://blog.csdn.net/m0_74932528/article/details/141069423

相关文章

  • 探索Python中的插入排序算法
    探索Python中的插入排序算法插入排序(InsertionSort)是一种简单直观的排序算法。虽然在大规模数据集上效率不如一些高级排序算法,但插入排序在处理小规模数据集或部分有序的数据时表现非常优秀。本文将介绍插入排序的工作原理、实现方法以及它的时间复杂度。插入排序的工作......
  • 力扣面试经典算法150题:移除元素
    移除元素今日的题目依旧是力扣面试经典算法150题中数组相关的题目:移除元素题目链接:https://leetcode.cn/problems/remove-element/description/?envType=study-plan-v2&envId=top-interview-150题目描述给定一个排序数组nums和一个值val,需要在原地移除数组中所有等......
  • 插入→面→移动面的作用是什么呢?是可以把一个面拉伸吗?
    问题描述:插入→面→移动面的作用是什么呢?是可以把一个面拉伸吗?问题解答:在SolidWorks中,“插入→面→移动面”工具的作用是修改现有零件的几何形状,它主要用来移动、拉伸、旋转或偏移指定的面。这个工具可以用于多种情况,包括调整零件尺寸、修改形状等。具体作用:移动面:你可......
  • 排序简单篇——冒泡排序、选择排序、插入排序、希尔排序、快速排序全解析【附完整源码
    ......
  • 151. 反转字符串中的单词【 力扣(LeetCode) 】
    一、题目描述  给你一个字符串s,请你反转字符串中单词的顺序。  单词是由非空格字符组成的字符串。s中使用至少一个空格将字符串中的单词分隔开。  返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。注意:输入字符串s中可能会存在前导空格、尾......
  • 【YashanDB数据库】由于网络带宽不足导致的jdbc向yashandb插入数据慢
    问题现象某客户环境,客户的业务使用jdbc驱动向其他操作系统上的yashandb插入90万条数据,耗时大约30分钟。问题的风险及影响影响客户的业务处理效率问题影响的版本所有的yashandb版本问题发生原因jdbc执行batchinsert时,是有绑定变量的。在准备好了PreparedStatement以后,jdbc......
  • 力扣第五十题——Pow(x,n)
    内容介绍实现 pow(x, n) ,即计算 x 的整数 n 次幂函数(即,xn )。示例1:输入:x=2.00000,n=10输出:1024.00000示例2:输入:x=2.10000,n=3输出:9.26100示例3:输入:x=2.00000,n=-2输出:0.25000解释:2-2=1/22=1/4=0.25提示:-100.0<x<100.0-2......
  • 力扣1.给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值
    1.给定一个整数数组nums和一个整数目标值target,请你在该数组中找出和为目标值target的那两个整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。letnums=[1,2,4,5,3,2,4,6......
  • 【数据结构与算法】在循环队列中第k个元素之后插入元素的算法 C++实现(循环队列+模运算
    数组a[MaxSize]用作一个循环队列,front指向循环队列中队头元素的前一个位置,rear指向队尾元素的位置。设计在队列中第k个元素之后插入item的算法。思路首先,检查输入的位置k是否在合理的范围内,即1到queueSize(Q)(包含两端)。如果k在这个范围外,那么返回ERROR。然后,计......
  • 算法力扣刷题记录 六十八【131.分割回文串】
    前言回溯章节第六篇。切割问题。记录六十八【131.分割回文串】。一、题目阅读给你一个字符串s,请你将s分割成一些子串,使每个子串都是回文串。回文串指字符串从前读和从后读一样。返回s所有可能的分割方案。示例1:输入:s="aab"输出:[["a","a","b"],["aa","b"]]......