作者：周月醉 | 来源：互联网 | 2023-09-15 12:03
public List merge(List intervals) {}
以上是题目和例子。
做法：（忘了是自己写出来的还是参考答案的orz）
1. 先把interval的start和end points分别取出来，放到array里，再用Array.sort(...)，把所有起点之间排序，然后把所有终止点之间排序。
2. 然后用一个for循环，循环过每一个interval，但是实际上查看的是，按大小排序的start point以及end point。设置两个指针，一个指向现在正在寻找的start point，一个指向现在正在寻找的end point。如果当前的end point大于等于下一个start point，就直接到下个interval接着找，如果当前的end point小于下一个start，就把现在的end point当做end，然后把之前预设的start当做start，组成一个interval塞进result list里。
3. Time complexity: O(nlogn) because of the sorting algorithm
Space complexity: O(n) because I am building a result list
我的代码：
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
class Solution {
public List merge(List intervals) {
int n = intervals.size();
int[] starts = new int[n];
int[] ends = new int[n];
for (int i = 0; i ) {
starts[i] = intervals.get(i).start;
ends[i] = intervals.get(i).end;
}
Arrays.sort(starts);
Arrays.sort(ends);
// loop through
List res = new ArrayList();
for (int i = 0, j = 0; i // j is start of interval.
if (i == n - 1 || starts[i + 1] > ends[i]) {
res.add(new Interval(starts[j], ends[i]));
j = i + 1;
}
}
return res;
}
}
有几个要注意的点：
1. 当iteration的指针移到最后一个的时候，无论如何都要把当前的interval塞进去。因为如果这个interval可以和之前的interval合并的话，end point已经更新到现在这个interval了，所以可以直接把当前interval加入到result里。如果这个interval不能和之前的interval合并，当前的interval也要当做一个单独的interval加入到result里面，因为最后一个不加不行。所以，在loop里面的if判断里，可以用一个 || 来同时包括两种情况。
2. variable定义要clean。
#56 Merge intervals
京公网安备 11010802041100号