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