66.构建乘积数组.md

66.构建乘积数组

题目描述

给定一个数组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²),空间复杂度为O(n)，显然是不符合要求的。

Java 代码如下：

    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;
    }

C++ 代码如下：

class Solution {
public:
    vector<int> multiply(const vector<int> &A) {
        vector<int> nums = vector<int>(A.size());
        if (A.size() > 0) {
            for (int i = 0; i < A.size(); i++) {
                int result = 1;
                for (int j = 0; j < A.size(); j++) {
                    // 跳过自身
                    if (j == i)
                        continue;
                    // 其他的都乘起来
                    result *= A[j];
                }
                nums[i] = result;
            }
        }
        return nums;
    }
};

再想想更优的做法，可以分解开看。最后的结果中，每一个数，都是等于它左边的所有数，乘以它右边的所有数。 那么我们可以申请一个数组，假设为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;
    }

C++ 实现如下：

class Solution {
public:
    vector<int> multiply(const vector<int> &A) {
        vector<int> B = vector<int>(A.size());
        // 初始化第一个值
        B[0] = 1;
        // 计算左边的乘积
        for (int i = 1; i < A.size(); i++)
            B[i] = B[i - 1] * A[i - 1];
        // 初始化临时变量
        int temp = 1;
        // 从右边往左边计算
        for (int i = A.size() - 2; i >= 0; i--) {
            // 计算右边的乘积
            temp *= A[i + 1];
            // 右边乘以左边
            B[i] *= temp;
        }
        return B;
    }
};

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