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

Question

我最近在电话中被问到以下面试问题：给定一个整数数组，生成一个数组，其值是除当前索引之外的所有其他整数的乘积。例子：[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

考虑位于 index 的元素i。看看它的左边，假设我们有一个元素的乘积，直到 index i-1。让我们称之为它leftProduct[i]是元素左侧的所有元素的乘积i。同样，让 callrightProduct[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本身。

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

Answer 2

我的想法：

• 获取产品所有数字并将其存储在变量中result。

• 现在，对于每个元素，答案是result / arr[i]。

• 因此，对每个元素从1toresult/2进行二分搜索arr[i]以获得quotient每个 arr[i] 的答案。

• 时间复杂度：O(n * (log(n))，空间复杂度：O(1)。