51-构建乘积数组

题⽬描述

给定⼀个数组A[0,1,...,n-1] ,请构建⼀个数组B[0,1,...,n-1] ，其中B 中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1] 。不能使⽤除法。（注意：规定B[0] =A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2] ）

对于A ⻓度为1 的情况，B⽆意义，故⽽⽆法构建，因此该情况不会存在。

输⼊：[1,2,3,4,5]
输出：[120,60,40,30,24]

思路及解答

暴力

由于这道题不可以使⽤除法，如果使⽤暴⼒做法的话，需要每⼀个数值，都计算其他所有数的乘积，那这样的算法时间复杂度是$O(n^2)$,空间复杂度为$O(n)$ ，显然是不符合要求的。

public int[] multiply(int[] A) {
    if (A != null) {
        int[] nums = new int[A.length];
        for (int i = 0; i < A.length; i++) {
            int result = 1;
            for (int j = 0; j < A.length; j++) {
                // 跳过⾃身
                if (j == i)
                    continue;
                // 其他的都乘起来
                result *= A[j];
            }
            nums[i] = result;
        }
        return nums;
    }
    return null;
}

分解计算

可以分解开看。最后的结果中，每⼀个数，都是等于它左边的所有数，乘以它右边的所有数。

那么我们可以申请⼀个数组，假设为B[] ，第⼀次遍历的数组A[] 的时候，把每⼀个数A[i] 左边的所有数的乘积，乘起来，放在B[i] 的位置。此时，每⼀个数左边的乘积已经有了，如何计算右边的乘积呢？

可以同样申请⼀个数组C[] 存起来，但是没有必要，因为我们从右边往左边遍历的时候，只需要⽤⼀个临时变量，把右边的乘积存着，和左边的乘积相乘，赋值到原来的数组A[] ，就可以了。

public int[] multiply(int[] A) {
    if (A == null || A.length < 2)
        return null;
    int[] B = new int[A.length];
    // 初始化第⼀个值
    B[0] = 1;
    // 计算左边的乘积
    for (int i = 1; i < A.length; i++)
        B[i] = B[i - 1] * A[i - 1];
    // 初始化临时变量
    int temp = 1;
    // 从右边往左边计算
    for (int i = A.length - 2; i >= 0; i--) {
        // 计算右边的乘积
        temp *= A[i + 1];
        // 右边乘以左边
        B[i] *= temp;
    }
    return B;
}

上⾯的做法相当于申请了⼤⼩为n 的临时空间，空间复杂度为O(n) ，遍历了数组两遍，时间复杂度为
O (2n) ，也就是O(n) 。