每天一道leetcode56-合并区间
- 2019 年 10 月 4 日
- 筆記
题目
每天一道leetcode56-合并区间 分类：数组 中文链接： https://leetcode-cn.com/problems/merge-intervals/description/ 英文链接 https://leetcode.com/problems/merge-intervals/description/
题目详述
给出一个区间的集合，请合并所有重叠的区间。 示例 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] 可被视为重叠区间。
题目详解
思路
- 首先根据数组中的第一个数字进行排序，[1,3][2,6][8,10]中的就是1,2,8根据这三个数字对二维数组中进行排序
- 排完序以后，这样二维数组中的数组就按照第一个数字的大小进行了排序，所以第一个数字是依次递增的
- 然后就去比较[1,3]中3与下一个数组中2和6比较大小，如果数字3在2和6之间说明这两个数组是可以合并的；合并完是[1,6]
- [1,6]继续与[8,10]合并，比较6与8,10，6是小于8的所以这个时候不能合并，只能二维数组的下标i进行i++的操作
- 这个还有一种情况就是比如是[1,10]与[2,8],10是大于8的这个时候，也可以进行合并
- 把这三种情况讨论一遍进行
代码
class Interval { int start; int end; Interval() { start = 0; end = 0; } Interval(int s, int e) { start = s; end = e; } } public List<Interval> merge(List<Interval> intervals) { Collections.sort(intervals, new Comparator<Interval>() { @Override public int compare(Interval o1, Interval o2) { if(o1.start > o2.start) return 1; else if(o1.start < o2.start) return -1; else return 0; } }); int i = 0; while(i < intervals.size()) { if(i != intervals.size() - 1) { if(intervals.get(i).end >= intervals.get(i+1).start && intervals.get(i).end <= intervals.get(i+1).end) { int tempStart = intervals.get(i).start; int tempEnd = intervals.get(i+1).end; intervals.remove(i); intervals.get(i).start = tempStart; intervals.get(i).end = tempEnd; }else if(intervals.get(i).end < intervals.get(i+1).start){ i++; }else if(intervals.get(i).end > intervals.get(i+1).end){ intervals.remove(i+1); i=i; } }else { i++; } } return intervals; }
代码讲解
- 10-20行就是根据第一个数字来进行排序
- 26行-32行就是去比较 [1,3] [2,6]（分别代表intervals.get(i) 和intervals.get(i+1)）中3满足了>=2 且 <= 6 然后就进行合并
- 33-34行就是[1,3] [5,7]中3 < 5了无法进行合并，i++
- 35-37行就是[1,10] [2,8] 中 10大于8也可以合并 （看到这里，你可能会有疑问为啥可以合并了，因为我们在10-20行已经根据第一个数字排序过了，所以前后两个数组中[a,3],[b,7]比如说这个，a是必然小于等于b的）
- 39-40行，最后一个元素，直接i++
