##給出一個區間的集合，請合并所有重疊的區間，
示例 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++;
}
結點的添加僅操作了地址，
鏈接：https://leetcode-cn.com/problems/merge-intervals
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/91957.html
標籤：其他
下一篇：什么是堆疊？