51.构建乘积数组.md

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];）。

 

解题思路

下面的思路来自《剑指offer》。

• 思路一，三角连乘。（==记得把下面的图片上传到自己的图床==，图片来源链接）

  见下面的图片，可以先把下半部分三角算出来，从上往下算，其中后一行的结果可以由前一行得到；然后再把上半部分的三角算出来，从下往上算，其中上一行的结果可以由下一行算出，可以设置一个temp变量，每次往该变量里面乘一个数，再乘到结果数组中。

  

 

代码

• 思路一，三角连乘。

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        int n = A.size();
        vector<int> B(n, 1);  // 初始化为n个数，全都为1
        
        for(int i=1; i<n; i++) B[i] = B[i-1]*A[i-1];
        
        int temp = A[n-1];
        for(int i=n-2; i>=0; i--){
            B[i] *= temp;
            temp *= A[i];
        }
        
        return B;
    }
};