插入区间
题目形容:给你一个 无重叠的,依照区间起始端点排序的区间列表。
在列表中插入一个新的区间,你须要确保列表中的区间依然有序且不重叠(如果有必要的话,能够合并区间)。
示例阐明请见 LeetCode 官网。
起源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权,非商业转载请注明出处。
解法一:遍历数组
- 首先如果 intervals 为空,因为不须要解决合并,所以间接返回一个区间 newInterval;
如果 intervals 不为空,申明 1 个变量 length 记录 intervals 的区间数,而后分以下几种状况进行解决:
- 如果新区间 newInterval 的最大值小于 intervals 所有区间的最小值,则不须要合并,将新区间放在 intervals 的最后面,而后返回;
- 如果新区间 newInterval 的最小值大于 intervals 所有区间的最大值,则不须要合并,将新区间放在 intervals 的最初面,而后返回;
如果后面两种状况不存在,则用 matchFirst 和 matchSecond 记录 newInterval 的 2 个数,newLength 为新区间的数量初始为 length+1,用一个 boolean 数组 flag 记录 intervals 有哪些区间被合并,而后遍历 intervals 的所有区间:
- curFirst 和 curSecond 为以后区间的 2 个数,用 matchFirst、matchSecond、curFirst、curSecond 判断 2 个区间是否相交,如果相交,则更新 matchFirst 和 matchSecond 的值,并且将以后区间的标识更新为已合并。
- 遍历实现后,初始化一个新的区间数组 newIntervals,将新区间
{matchFirst, matchSecond}
和 intervals 放入 newIntervals 中没有被合并的区间放入 newIntervals 中(须要判断将新区间放在适合的地位),而后返回 newIntervals。
public class LeetCode_057 {public static int[][] insert(int[][] intervals, int[] newInterval) {if (intervals == null || intervals.length == 0) {return new int[][]{newInterval};
}
int length = intervals.length;
if (newInterval[1] < intervals[0][0]) {
// 如果新区间的最大值小于所有区间的最小值,则不须要合并,将新区间放在 intervals 的最后面
int[][] newIntervals = new int[length + 1][2];
newIntervals[0] = newInterval;
for (int i = 0; i < length; i++) {newIntervals[i + 1] = intervals[i];
}
return newIntervals;
} else if (newInterval[0] > intervals[length - 1][1]) {
// 如果新区间的最小值大于所有区间的最大值,则不须要合并,将新区间放在 intervals 的最初面
int[][] newIntervals = new int[length + 1][2];
for (int i = 0; i < length; i++) {newIntervals[i] = intervals[i];
}
newIntervals[length] = newInterval;
return newIntervals;
} else {int matchFirst = newInterval[0], matchSecond = newInterval[1], newLength = length + 1;
boolean[] flag = new boolean[length];
for (int i = 0; i < length; i++) {int curFirst = intervals[i][0], curSecond = intervals[i][1];
if (((matchFirst >= curFirst && matchFirst <= curSecond) || (matchSecond >= curFirst && matchSecond <= curSecond)) ||
((curFirst >= matchFirst && curFirst <= matchSecond) || (curSecond >= matchFirst && curSecond <= matchSecond))) {
// 有交加
matchFirst = Math.min(matchFirst, curFirst);
matchSecond = Math.max(matchSecond, curSecond);
flag[i] = true;
newLength--;
}
}
int[][] newIntervals = new int[newLength][2];
boolean added = false;
int pos = 0;
for (int i = 0; i < length; i++) {if (!flag[i]) {if (added) {newIntervals[pos++] = intervals[i];
} else {if (matchSecond < intervals[i][0]) {newIntervals[pos++] = new int[]{matchFirst, matchSecond};
added = true;
}
newIntervals[pos++] = intervals[i];
}
}
}
if (!added) {newIntervals[pos++] = new int[]{matchFirst, matchSecond};
}
return newIntervals;
}
}
public static void main(String[] args) {int[][] intervals = new int[][]{{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}};
int[] newInterval = new int[]{4, 8};
for (int[] ints : insert(intervals, newInterval)) {for (int anInt : ints) {System.out.print(anInt + " ");
}
System.out.println();}
}
}
【每日寄语】明天也是值得你用可恶和温顺去看待的一天呀。