一、题目描述
示例 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]重叠。
二、解题思路
-
初始化结果列表：创建一个列表来存储最终的区间结果。
-
遍历区间：遍历
intervals数组和newInterval，对于每个区间，检查它与newInterval的关系。 -
处理区间：如果当前区间与
newInterval不重叠，直接将其添加到结果列表中。如果重叠，需要将newInterval与当前区间合并，并将合并后的区间添加到结果列表中。 -
返回结果：将结果列表转换为二维数组并返回。
三、具体代码
import java.util.ArrayList;
import java.util.List;
public class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> result = new ArrayList<>();
int start = newInterval[0];
int end = newInterval[1];
for (int[] interval : intervals) {
if (interval[0] > end) {
// 当前区间在newInterval的右侧，直接添加到结果中
result.add(new int[]{start, end});
start = interval[0];
end = interval[1];
} else if (interval[1] < start) {
// 当前区间在newInterval的左侧，不需要合并，直接添加到结果中
result.add(interval);
} else {
// 当前区间与newInterval有重叠，需要合并
// 更新start和end为合并后的区间的起始和结束点
start = Math.min(start, interval[0]);
end = Math.max(end, interval[1]);
}
}
// 添加最后一个区间
result.add(new int[]{start, end});
// 将列表转换为二维数组并返回
return result.toArray(new int[0][0]);
}
public static void main(String[] args) {
Solution sol = new Solution();
int[][] intervals = {{1,2},{3,5},{6,7},{8,10},{12,16}};
int[] newInterval = {4,8};
int[][] result = sol.insert(intervals, newInterval);
for (int[] interval : result) {
System.out.println("[" + interval[0] + ", " + interval[1] + "]");
}
}
}四、时间复杂度和空间复杂度
1. 时间复杂度
- 时间复杂度是O(n)。
- 该算法的主要操作是遍历
intervals数组中的每个区间，并与newInterval进行比较和合并。 - 这个操作是线性的，因为它只涉及一次遍历，所以时间复杂度为O(n)，其中n是
intervals数组的长度。
2. 空间复杂度
- 空间复杂度是O(n)。
- 算法中使用了一个
List<int[]>来存储结果，最坏情况下，这个列表将包含所有原始区间加上newInterval。因此，空间复杂度为O(n)，其中n是intervals数组的长度。 - 由于
result.toArray(new int[0][0])这一行代码，算法还需要额外的空间来创建一个二维数组。这个数组的大小最多为intervals的长度加1，所以这部分的空间复杂度也是O(n)。
五、总结知识点
-
二维数组（int[][] intervals）：用于存储区间列表，其中每个区间由一个包含两个整数的数组表示。
-
一维数组（int[] newInterval）：表示要插入的单个区间。
-
ArrayList 和 List 接口：用于动态存储和管理区间。
ArrayList是一个可动态扩展和收缩的数组实现，提供了灵活的添加、删除和访问元素的方法。 -
for-each 循环：用于遍历数组和列表中的元素。这是一种简洁的循环语法，允许我们直接访问集合中的每个元素，而不需要处理迭代器或索引。
-
条件语句（if-else）：用于根据不同的条件执行不同的代码块。在这个例子中，我们根据区间的位置和关系来决定是否合并区间。
-
数组操作：包括创建数组、访问数组元素和修改数组元素的值。
-
Math.min 和 Math.max 方法：用于计算两个数值中的最小值和最大值，这在合并区间时非常有用。
-
toArray 方法：
List接口的toArray方法用于将列表转换为数组。在Java中，如果目标数组的类型与列表中元素的类型不匹配，需要指定目标数组的类型。 -
方法的返回值：方法
insert返回一个二维数组，表示合并后的区间列表。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。
标签：newInterval,--,57,interval,int,intervals,数组,区间,LeetCode From： https://blog.csdn.net/weixin_62860386/article/details/136997186