您好,登录后才能下订单哦!
小编给大家分享一下LeetCode怎么插入区间,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!
1,问题简述
给出一个无重叠的 ,按照区间起始端点排序的区间列表。在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。
2,示例
示例 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] 重叠。
注意:输入类型已在 2019 年 4 月 15 日更改。请重置为默认代码定义以获取新的方法签名。
3,题解思路
其实这道题和前面的合并区间那道题的整个题解思路是一样的,将新数组元素装入到集合里面,然后将集合元素排序一下,然后进行逻辑判断,这里使用了集合作为一个临时存储空间,比较相邻区间的内容,如前一个区间右端点的值和下一个区间左端点的值做比较,符合合并的时候进行合并之后放入结果集,不符合合并的也放入结果集中,当所有的区间都处理完成之后,符合合并的数据就处理完成了,这也是本题的主要思路
4,题解程序
import java.util.*;
public class InsertTest {
public static void main(String[] args) {
int[][] intervals = {
{1, 3},
{6, 9}
};
int[] newInterval = {2, 5};
int[][] insert = insert(intervals, newInterval);
for (int[] arr : insert) {
System.out.println(arr[0] + " " + arr[1]);
}
}
public static int[][] insert(int[][] intervals, int[] newInterval) {
if ((intervals == null) && newInterval == null) {
return new int[][]{newInterval};
}
List<int[]> list = new ArrayList<>();
Collections.addAll(list, intervals);
list.add(newInterval);
int[][] tempArray = list.toArray(new int[0][]);
List<int[]> result = new ArrayList<>();
Arrays.sort(tempArray, Comparator.comparingInt(x -> x[0]));
List<int[]> tempList = new ArrayList<>();
Collections.addAll(tempList, tempArray);
int[] temp = tempList.get(0);
for (int i = 1; i < tempList.size(); i++) {
if (tempList.get(i)[0] <= temp[1]) {
temp = new int[]{temp[0], Math.max(temp[1], tempList.get(i)[1])};
} else {
result.add(temp);
temp = tempList.get(i);
}
}
result.add(temp);
int[][] array = result.toArray(new int[0][]);
return array;
}
}
5,题解程序图片版
以上是“LeetCode怎么插入区间”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注亿速云行业资讯频道!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。