java - 给定一个数字数组，不除法返回所有其他数字的乘积数组？

Question

我最近在电话中被问到以下面试问题:

Given an array of integers, produce an array whose values are the product of every other integer excluding the current index.

Example:

[4, 3, 2, 8] -> [3*2*8, 4*2*8, 4*3*8, 4*3*2] -> [48, 64, 96, 24]

我想出了下面的代码:

public static BigInteger[] calcArray(int[] input) throws Exception {
    if (input == null) {
        throw new IllegalArgumentException("input is null");
    }
    BigInteger product = calculateProduct(input);
    BigInteger result[] = new BigInteger[input.length];
    for (int i = 0; i < input.length; i++) {
        result[i] = product.divide(BigInteger.valueOf(input[i]));
    }
    return result;
}

private static BigInteger calculateProduct(int[] input) {
    BigInteger result = BigInteger.ONE;
    for (int i = 0; i < input.length; i++) {
        result = result.multiply(BigInteger.valueOf(input[i]));
    }
    return result;
}

复杂度:

Time Complexity: O(n)
Space Complexity: O(n)

我们能否在不除法的情况下以 O(n) 的复杂度做到这一点？如果使用简单的原始整数数组，还有什么方法可以降低空间复杂度。

Answer 1

考虑一个位于索引 i 的元素.看看它的左边，假设我们有一个元素的乘积，直到索引 i-1 .让我们称之为leftProduct[i]这是 i 处元素左侧所有元素的乘积.同样让我们调用rightProduct[i]是 i 处元素右侧所有元素的乘积. 那么该索引的结果是 output[i] = leftProduct[i]*rightProduct[i]

现在想想怎么得到leftProduct .您只需从头开始遍历数组并计算一个正在运行的产品，然后在每个元素处更新 leftProduct与当前运行的产品。 同样，您可以计算 rightProduct通过从末尾遍历数组。在这里您可以通过重用 leftProduct 来优化空间。通过乘以 rightProduct 来更新数组.

下面的代码演示了这一点:

public static int[] getProductsExcludingCurrentIndex( int[] arr ) {
     if ( arr == null || arr.length == 0 ) return new int[]{};
     int[] leftProduct = new int[arr.length];
     int runningProduct = 1;
     //Compute left product at each i
     for ( int i = 0; i < arr.length; i++ ) {
       leftProduct[i] = runningProduct;
       runningProduct = runningProduct*arr[i];
    }
    runningProduct = 1;
    //By reverse traversal, we compute right product but at the same time update the left 
    //product, so it will have leftProduct*rightProduct
    for ( int i = arr.length - 1; i >= 0; i-- ) {
        leftProduct[i] = leftProduct[i]*runningProduct;
        runningProduct = runningProduct*arr[i];
    }
    return leftProduct;
}

空间复杂度为 O(n) - 我们只使用一个数组 leftProduct ，时间复杂度为O(n) .

• 空间复杂度编辑:

但是如果你不考虑用于存储输出的空间，那么这是 O(1) ，因为我们将输出存储在 leftProduct 中本身。

如果您绝对不想要额外的空间，则需要修改您的输入数组。至少据我所知，通过随时修改输入数组来解决这个问题是不可能的。