为什么 'count' 的值没有在不同的递归中保留？

Question

这是 Java 计算数组反转的代码。

private void findInversions(int begin, int end, Integer count) {
    System.out.println("begin: " + begin + ", end: " + end + ", and count is " + count);
    if (end - begin < 1)
        return;
    int middle = (begin + end) / 2;
    findInversions(begin, middle, count);
    System.out.println("begin: " + begin + ", end: " + end + ", here count is " + count);
    findInversions(middle + 1, end, count);
    mergeAndCount(begin, middle, end, count);
    System.out.println("begin: " + begin + ", end: " + end + ", count now is: " + count);
}



private void mergeAndCount(int begin, int middle, int end, Integer count) {

    int[] result = new int[end - begin + 1];
    int aptr = begin;
    int bptr = middle + 1;
    for (int i = 0; i < result.length; i++) {
        if (aptr <= middle && bptr <= end) {
            if (numbers[aptr] < numbers[bptr]) {
                result[i] = numbers[aptr];
                aptr++;
            }
            else { // numbers[aptr] > numbers[bptr]
                // (a[aptr], b[bptr]) is an inversion here
                count++;
                System.out.println("Found: (" + numbers[aptr] + "," + numbers[bptr] + ") " + count);
                result[i] = numbers[bptr];
                bptr++;
            }
        }
        else if (aptr > middle) {
            result[i] = numbers[bptr];
            bptr++;
        }
        else if (bptr > end) {
            result[i] = numbers[aptr];
            aptr++;
        }

    }

    for (int i = 0; i < result.length; i++) {
        numbers[begin + i] = result[i];
    }

}

反转打印得很好，但是 count 永远不会正确，因为它在递归调用 returns 后失去了价值。我已经调试了几次，我所看到的只是 count 在递归结束时再次变为 0，但我找不到原因。谁能解释一下？

Answer 1

Integer 是不可变的 class。当执行 count++ 时，值自动拆箱为 int，此 int 递增并将结果分配给 count。但是你不修改你塞进方法中的实例。你可以。 G。使用 AtomicInteger 实例并使用 incrementAndGet() 或 getAndIncrement() 方法。

Answer 2

您的 mergeAndCount() 方法应该 return 它获得的计数。调用这些方法的方法应该使用 return 值。我将它保留为 Integer 但没有必要；你可以使用原语 int.

private Integer findInversions(int begin, int end, Integer count) {
    // ... do all your stuff here but change recursive calls:
    count += findInversions(begin, end, count);
    count += mergeAndCount(begin, middle, end, count0;
    // and return what you find
    return count;
}

private Integer mergeAndCount(int begin, int middle, int end, Integer count) {
    // ... do all your stuff here
    return count;
}

由于 numbers 显然是您计数 class 中的一个字段，您的另一个选择是将 count 保留为 class 中的一个字段。那将与您所寻求的效果相同。

为什么 'count' 的值没有在不同的递归中保留？

Why is the value of 'count' not kept across different recursions?

java

recursion

pass-by-reference