0
我在interval上工作，它存在於ArrayList及其start屬性中，interval的完整定義將在示例代碼中顯示爲私有類。歸併上的ArrayList只的ArrayList（收藏<? extends E> c）不的ArrayList（INT參數：initialCapacity）工作？
我使用的實現是MergeSort，並且非常相似，Princeton's stuff我參考一下，但問題是我覺得這個實現只有合作創建輔助ArrayList aux與ArrayList(Collection<? extends E> c)與aux.set(i, intervals.get(i));初始化它試圖填補aux與interval來自原始列表的項目
我嘗試着創建aux與ArrayList(int initialCapacity)並用aux.add(intervals.get(i))初始化它，但是失敗。我仍然無法弄清楚，爲什麼這樣不行？
完整的代碼，可以直接用於調試：
public class Test {
private class Interval {
// Will use start property to sort
int start;
int end;
Interval() {
start = 0;
end = 0;
}
Interval(int s, int e) {
start = s;
end = e;
}
@Override
public String toString() {
return "[" + start + "," + end + "]";
}
}
public void sortHelper(List<Interval> intervals) {
int len = intervals.size();
// Only this way works
List<Interval> aux = new ArrayList<Interval>(intervals);
// This way NOT work ?
//List<Interval> aux = new ArrayList<Interval>(len);
sort(intervals, aux, 0, len - 1);
}
public void sort(List<Interval> intervals, List<Interval> aux, int lo, int hi) {
if(hi <= lo) {
return;
}
int mid = lo + (hi - lo)/2;
sort(intervals, aux, lo, mid);
sort(intervals, aux, mid + 1, hi);
mergeHelper(intervals, aux, lo, mid, hi);
}
public void mergeHelper(List<Interval> intervals, List<Interval> aux, int lo, int mid, int hi) {
// Only this way works
for(int i = lo; i <= hi; i++) {
aux.set(i, intervals.get(i));
}
// Combine with List<Interval> aux = new ArrayList<Interval>(len);
// this way NOT work ?
//for(int i = lo; i <= hi; i++) {
// aux.add(intervals.get(i));
//}
int left = lo;
int right = mid + 1;
for(int k = lo; k <= hi; k++) {
if(left > mid) {
intervals.set(k, aux.get(right++));
} else if(right > hi) {
intervals.set(k, aux.get(left++));
} else if(less(aux.get(right), aux.get(left))) {
intervals.set(k, aux.get(right++));
} else {
intervals.set(k, aux.get(left++));
}
}
}
public boolean less(Interval a, Interval b) {
return a.start - b.start < 0;
}
public static void main(String[] args) {
Test m = new Test();
Interval one = m.new Interval(1, 3);
Interval two = m.new Interval(2, 6);
Interval three = m.new Interval(8, 10);
Interval four = m.new Interval(15, 18);
List<Interval> intervals = new ArrayList<Interval>();
// Adding order as [2,6],[1,3],[8,10],[15,18]
intervals.add(two);
intervals.add(one);
intervals.add(three);
intervals.add(four);
m.sortHelper(intervals);
// Expected sort result should be
// [1,3],[2,6],[8,10],[15,18]
for(Interval i : intervals) {
System.out.println(i);
}
}
}
誰能幫助我理解爲什麼必須建立輔助ArrayList aux與ArrayList<Collection<? extends E> c>與aux.set(i, intervals.get(i));初始化呢？或者我的理解錯誤？ 感謝
@maraca，謝謝，但你能仔細檢查一遍，其實我沒有使用與原始類型ArrayList中，該ArrayList只是一個構造函數我用於初始化長度有限的ArrayList，實際項目是'Interval'類型，聲明爲私有類 –
Lampard
是的，我在代碼中看到並刪除了註釋。但是你的兩條線並不相同，一條是製作一個副本，另一條是創建一個具有一定容量的空數組。 – maraca
@maraca，沒錯，我知道這兩個構造函數的區別，但問題是爲什麼需要這樣的原始列表副本？只是初始化一個新的空列表，然後從原始列表中添加相同的訂單項將無法與MergeSort一起使用，甚至更多，如果您只是使用'new ArrayList（間隔）'來複制一個列表而不是**'aux.set （i，intervals.get（i））;'也行不通，這些東西讓我困惑，如果你有時間可以在IDE上運行的行爲，謝謝 –
Lampard