其他
472,插入区间
If we cease to believe in love, why would we want to live?
如果我们不相信爱,那又为何而活呢?
问题描述
给出一个无重叠的 ,按照区间起始端点排序的区间列表。
在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。
示例 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] 重叠。
先计算两边再计算中间
这里我们人为把数组分为3部分,左边不重合的(如果有)添加到集合list中,右边不重合的(如果有)也添加到集合list中,然后再合并中间的,这里以示例2为例画个图看一下
原理很简单,来看下代码
1public int[][] insert(int[][] intervals, int[] newInterval) {
2 //边界条件判断
3 if (intervals.length == 0)
4 return new int[][]{newInterval};
5 List<int[]> resList = new ArrayList<>();
6
7 //一个从左边开始找不重合的
8 int left = 0;
9 //一个从右边开始找不重合的
10 int right = intervals.length - 1;
11
12 //左边不重合的添加到list中
13 while (left < intervals.length && intervals[left][1] < newInterval[0]) {
14 resList.add(intervals[left++]);
15 }
16
17 //右边不重合的添加到list中
18 while (right >= 0 && intervals[right][0] > newInterval[1]) {
19 resList.add(left, intervals[right--]);
20 }
21
22 //下面一大坨是合并中间重合的,注意一些边界条件的判断
23 int[] newArr = new int[2];
24 newArr[0] = left >= intervals.length ? newInterval[0] : Math.min(intervals[left][0], newInterval[0]);
25 newArr[1] = right < 0 ? newInterval[1] : Math.max(intervals[right][1], newInterval[1]);
26 resList.add(left, newArr);
27
28 //这一大坨是把list转二维数组
29 int[][] resArr = new int[resList.size()][2];
30 for (int i = 0; i < resList.size(); i++) {
31 resArr[i] = resList.get(i);
32 }
33 return resArr;
34}
35
逐步合并
上面一种方式是先把两边不重合的添加到集合list中,之后在合并中间的。这里还可以从左边开始把不重合的(如果有不重合的)添加到集合list中,如果遇到重合的就找出重合的范围然后再添加到集合中,最后再把后面不重合的(如果有)添加到集合list中。
1public int[][] insert(int[][] intervals, int[] newInterval) {
2 List<int[]> resList = new ArrayList<>();
3 int i = 0;
4 //先把前面不重合的添加到list中
5 while (i < intervals.length && intervals[i][1] < newInterval[0])
6 resList.add(intervals[i++]);
7
8 int mergeStar = newInterval[0];
9 int mergeEnd = newInterval[1];
10 //前面不重合的都添加到集合list中了,从这里开始就出现重合了,我们要找到重合的开始和结束值
11 while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
12 mergeStar = Math.min(mergeStar, intervals[i][0]);
13 mergeEnd = Math.max(mergeEnd, intervals[i][1]);
14 i++;
15 }
16 //然后再把重合的添加到list中
17 resList.add(new int[]{mergeStar, mergeEnd});
18
19 //把剩下的在添加到集合list中
20 while (i < intervals.length)
21 resList.add(intervals[i++]);
22
23 //这一大坨是把list转二维数组
24 int[][] resArr = new int[resList.size()][2];
25 for (int j = 0; j < resList.size(); j++) {
26 resArr[j] = resList.get(j);
27 }
28 return resArr;
29}
总结
这题难度不是很大,但一次写出来不出错比较困难,因为他有很多边界条件的判断。
长按上图,识别图中二维码之后即可关注。
如果觉得有用就点个"赞"吧