示例 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] 可被视为重叠区间。
思路
将区间按照左端点升序排列，同《算法导论》——活动选择问题。
时间复杂度O(nlgn)，空间复杂度O(n)。
代码
class Solution {
public int[][] merge(int[][] intervals) {
int length = intervals.length;
if(length < 2) return intervals;
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
if(a[0] == b[0]) {
return b[1] - a[1];
} else {
return a[0] - b[0];
}
}
});
List<int[]> ans = new LinkedList<int[]>();
int x = intervals[0][0];
int y = intervals[0][1];
for(int i = 1; i < length; i++) {
if(intervals[i][0] > y) {
ans.add(new int[]{x, y});
x = intervals[i][0];
y = intervals[i][1];
} else if(intervals[i][1] > y) {
y = intervals[i][1];
}
}
ans.add(new int[]{x, y});
int n = 0;
int[][] res = new int[ans.size()][2];
for(int[] i : ans) {
res[n][0] = i[0];
res[n++][1] = i[1];
}
return res;
}
}
笔记
-
ArrayList和LinkedList的大致区别：
1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
2.对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。
3.对于新增和删除操作add和remove，LinkedList比较占优势，因为ArrayList要移动数据。 -
ans.add(new int[]{x, y})
add方法只会将引用地址放入集合中,每次add需要new一个对象。
add函数源码：
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* Links e as last element.
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
结点的添加仅操作了地址。