【剑指offer】构建乘积数组

考察知识点：数组

题目描述

给定一个数组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]。不能使用除法。

题解

题解一：双层 for 循环

分析

B[0]=A[1]*A[2]*.....*A[n-1]，缺 A[0]
B[1]=A[0]*A[2]*.....*A[n-1]，缺 A[1]
B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]，缺 A[i]
观察出规律，B[i] 为 A 数组遍乘，当 A B 数组下标一致时跳过不乘

代码

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

题解二：优化

分析

我们用个小点的数据来模拟上面的解法，
A = [1,2,3,4,5]，即 A 的长度为 5

B[0] = A[1] $A[2] A[3] A[4]$
B[1] = A[0] $A[2] A[3] A[4]$
B[2] = A[0] $A[1] A[3] A[4]$
B[3] = A[0] $A[1] A[2] A[4]$
B[4] = A[0] $A[1] A[2] A[3]$

可以发现，有很多地方被重复计算了，我们优化的目标就是这些被大量重复计算的数值
换个角度观察，根据对角线拆分成
下三角：

B[0] = 1
B[1] = A[0] = B[0] $A[0]$
B[2] = A[0] $A[1] = B[1] A[1]$
B[3] = A[0] $A[1] A[2] = B[2] A[2]$
B[4] = A[0] $A[1] A[2] A[3] = B[3] A[3]$

即每一项 B[i] 都可以由上一项 B[i-1] 乘上 A[i-1] 得到
和上三角：

B[0] = B[0] $A[1] A[2] A[3] A[4]$
B[1] = B[1] $A[2] A[3] A[4]$
B[2] = B[2] $A[3] A[4]$
B[3] = B[3] $A[4]$
B[4] = 1

即每一项 B[i] 都可以由下一项 B[i+1] 乘上 A[i+1] 得到
上三角和下三角的乘积为最终答案

代码

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        int n = A.size();
        vector<int> B(n,1);
        // 计算下三角
        for(int i=1;i<n;i++)
            B[i] = B[i-1] * A[i-1];
        int temp = 1;
        // 计算上三角
        for(int i=n-2;i>=0;i--){
            temp *= A[i+1];
            B[i] *= temp;
        }
        return B;
    }
};