本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer，已开源在github ，欢迎star！
56. 合并区间
本题来自LeetCode：56. 合并区间[1]
题目描述
给出一个区间的集合，请合并所有重叠的区间。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
题目分析
题目解答
class Solution {
public int[][] merge(int[][] intervals) {
if(intervals == null || intervals.length == 0) {
return intervals;
}
// 排序
Arrays.sort(intervals, (o1, o2) - Integer.compare(o1[0], o2[0]));
// 上一个区间的位置
int preIndex = 0;
int k = 1;
while(k intervals.length) {
// 表示有重叠
if(intervals[k][0] = intervals[preIndex][1]) {
intervals[preIndex][1] = Math.max(intervals[preIndex][1], intervals[k][1]);
} else {
// 无重叠
intervals[++preIndex] = intervals[k];
}
k ++;
}
return Arrays.copyOf(intervals, preIndex + 1);
}
}
复杂度分析：
时间复杂度：
O(nlogn)，主要耗时为
TimSort排序
空间复杂度：
O(1)
57. 插入区间
本题来自LeetCode：57. 插入区间[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] 重叠。
题目分析
题目解答
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
int n = intervals.length;
int[][] newIntervals = new int[n + 1][2];
int count = 0;
int i = 0;
// 1. 找到重叠区间的起始区间
while(i n) {
if(newInterval[0] = intervals[i][0] || (newInterval[0] intervals[i][0] && newInterval[0] = intervals[i][1])) {
break;
}
newIntervals[count ++] = intervals[i ++];
}
// 2. 合并重叠区间
while(i n && newInterval[1] = intervals[i][0]) {
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
i ++;
}
// 3. 将合并的区间加入
newIntervals[count ++] = newInterval;
// 4. 将未重叠的区间加入
while(i n) {
newIntervals[count ++] = intervals[i ++];
}
return count == n + 1 ? newIntervals : Arrays.copyOf(newIntervals, count);
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(1)
参考资料
原文始发于微信公众号（xiaogan的技术博客）：
