【剑指offer】构建乘积数组

题目描述

给定一个数组 $A[0,1,...,n-1]$A[0,1,...,n−1],请构建一个数组 $B[0,1,...,n-1]$B[0,1,...,n−1],其中 $B$B 中的元素 $B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]$B[i]=A[0]∗A[1]∗...∗A[i−1]∗A[i+1]∗...∗A[n−1]。不能使用除法。

解题思路

方法一：
最简单的想法就是遍历数组 $A$A，只要下标和数组 $B$B 的不同，都进行相乘操作，例如，先取 $A[0]$A[0]，然后遍历数组 $B$B，除了 $B[0]$B[0]之外，$B[j](j\neq 0$B[j](j​=0)均乘上$A[0]$A[0]，$B[j]=B[j]*A[0]$B[j]=B[j]∗A[0]。可见，时间复杂度为$O(n^{2})$O(n2)。

实现代码：

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        int len = A.size();
        vector<int> B(len,1);
        for(int i=0;i<len;i++){
            for(int j=0;j<len;j++){
                if(i == j){
                    continue;
                }
                B[j] *= A[i];
            }
        }
        return B;
    }
};

方法二:
《剑指offer》书上提供的解决办法，$B[i]$B[i] 的值可以看作下图的矩阵中每行的乘积。

下三角计算比较容易，对数组 $A$A 进行遍历连乘就可以得到；上三角反过来看，也就是下三角，从下向上连乘就可以额得到。所以先算下三角中的连乘，即先算出 $B[i]$B[i] 中的一部分，然后倒过来按上三角中的分布规律，把另一部分也乘进去。

详细的计算过程如下：设有数组大小为5。
对于第一个for循环：
第一步：b[1] = b[0] * a[0] = a[0];
第二步：b[2] = b[1] * a[1] = a[0] * a[1];
第三步：b[3] = b[2] * a[2] = a[0] * a[1] * a[2];
第四步：b[4] = b[3] * a[3] = a[0] * a[1] * a[2] * a[3];

然后对于第二个for循环：
第一步：
temp *= a[4] = a[4];
b[3] = b[3] * temp = a[0] * a[1] * a[2] * a[4];
第二步：
temp *= a[3] = a[4] * a[3];
b[2] = b[2] * temp = a[0] * a[1] * a[4] * a[3];
第三步：
temp *= a[2] = a[4] * a[3] * a[2];
b[1] = b[1] * temp = a[0] * a[4] * a[3] * a[2];
第四步：
temp *= a[1] = a[4] * a[3] * a[2] * a[1];
b[0] = b[0] * temp = a[4] * a[3] * a[2] * a[1];

由此可以看出从b[4]到b[0]均已经得到正确计算。(以上的计算步骤参考牛客网，详情见底下链接)

实现代码：

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        int len = A.size();
        vector<int> B(len,1);
        for(int i=1;i<len;i++){
            B[i] = B[i-1]*A[i-1];
        }
        int temp =1;
        for(int i=len-2;i>=0;i--){
            temp *=A[i+1];
            B[i] *= temp;
        }
        return B;
    }
};

参考：

1. https://www.nowcoder.com/profile/1878117/codeBookDetail?submissionId=13951708