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

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