构建乘积数组

题目描述

给定一个数组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[i为分界],分为两个数组.

• B为两数组相乘

  
  

AC代码

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

看了讨论区

优化一下
其实Cn和Bn在同一循环条件内可合并.其实也不许要额外构建数组.
再优化一下,不需要数组,在循环中使用额外变量即可

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