0

我正在尝试构建一个区间树。在这一部分中，我必须按升序取所有左端点，按升序取所有右端点，并将它们放在一个单点列表中（不重复）。但是，当我尝试将正确的端点合并到点列表中时，我不断收到 indexOutOfBounds 异常。我已经确保了容量，这样就不会发生这种情况，但无论如何都会发生。我在这里不明白什么？

public static ArrayList<Integer> getSortedEndPoints(ArrayList<Interval> leftSortedIntervals, ArrayList<Interval> rightSortedIntervals) {

    ArrayList<Integer> result = new ArrayList<Integer>();

    for (int i = 0 ; i < leftSortedIntervals.size() ; i++ ) {

        if (i >= 1 && leftSortedIntervals.get(i-1).leftEndPoint != leftSortedIntervals.get(i).leftEndPoint ) {
        result.add(leftSortedIntervals.get(i).leftEndPoint);
        }
        else if (i == 0) {

            result.add(leftSortedIntervals.get(i).leftEndPoint);

        }

    }
    result.ensureCapacity(rightSortedIntervals.size()*2);
    for (int j = 0 ; j < rightSortedIntervals.size(); j++) {
        boolean duplicate = false;
        int size = result.size()-1;
        int temp = rightSortedIntervals.get(j).rightEndPoint;
        while (size >= 0 && result.get(size) >= rightSortedIntervals.get(j).rightEndPoint ) {
            if (result.get(size) == rightSortedIntervals.get(j).rightEndPoint) {
                duplicate = true;
                break;
            }
            else {
                result.set(size+1, result.get(size));

                size--;
            }


        }
        if (duplicate = true) {

            continue;

        }
        else {
        result.add(size, temp);
        }
    }


    return result;
}

错误发生在这一行：

else {
            result.set(size+1, result.get(size));

            size--;
        }
4

2 回答 2

2

你有：

int size = result.size() - 1;
// ...
result.set(size + 1, result.get(size));
size--;

因此每次都会发生错误：在第一次迭代中，size + 1 == result.size()所以你不能调用result.set(size+1, anything)

于 2013-03-13T19:48:48.843 回答
0

ensureCapacity 不会做你认为它做的事情。

ArrayList 有两个不同的值，大小和容量。容量是底层阵列中的存储量，但这不会向用户公开。大小是集合中考虑的元素数量，这在与它交互时很重要。

容量函数存在的唯一原因是，如果您事先知道要使用多少个元素，则增加容量可以让您添加元素，而不会潜在地缓慢地重新分配数组。

于 2013-03-13T19:50:45.227 回答