构建乘积数组

给定一个数组$A[0,1,...,n-1]A[0,1,...,n-1]$A[0,1,...,n−1],请构建一个数组$B[0,1,...,n-1]B[0,1,...,n-1]$B[0,1,...,n−1],其中B中的元素$B\left[i\right]=A\left[0\right]\ast A\left[1\right]\ast ...\ast A[i-1]\ast A[i+1]\ast ...\ast A[n-1]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]。不能使用除法。（注意：规定$B\left[0\right]=A\left[1\right]\ast A\left[2\right]\ast ...\ast A[n-1]，B[n-1]=A\left[0\right]\ast A\left[1\right]\ast ...\ast A[n-2]B[0]\; =\; A[1]\; *\; A[2]\; *\; ...\; *\; A[n-1]，B[n-1]\; =\; A[0]\; *\; A[1]\; *\; ...\; *\; A[n-2]$B[0]=A[1]∗A[2]∗...∗A[n−1]，B[n−1]=A[0]∗A[1]∗...∗A[n−2];） 对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在。

题意：给一个a数组构建一个b数组对于b数组的第i位为除了a数组第i为的其他值的乘积

案例
输入：[1,2,3,4,5]
返回值：[120,60,40,30,24]
答案第一位为2 * 3 * 4 * 5 = 120 第二位为 1 * 3 * 4 * 5= 60 以此类推

方法一: 暴力

暴力模拟题意

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> ans;
        for(int i = 0 ; i < A.size(); i ++){ //遍历每一位
            int res = 1;
            for(int j = 0; j < A.size(); j ++){ // 对于每一位暴力乘起来
                if(i != j) res *= A[j];
            }
            ans.push_back(res);
        }
        return ans;
    }
};

时间复杂度: $O\left(n^2\right)O(n^2)$O(n2) 对于每一位会遍历n次所以总复杂度为$O\left(n^2\right)O(n^2)$O(n2)

空间复杂度: $O\left(n\right)O(n)$O(n) 用来存储答案会存入n个元素

方法二: 前缀后缀乘积

首先对于第i位将前$1->i-11\; ->\; i-1$1−>i−1 位的数乘积存入数组中,类似与前缀和的思想,这样每个数会缺少 $i+1->ni+1\; ->\; n$i+1−>n的乘积类似后缀和的思想，所以从最后一位向前遍历并将$i+1->ni+1\; ->\; n$i+1−>n的乘积乘到第i位中最后的结果就是答案

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> ans;
        for(int i = 0; i < A.size(); i ++){ //记录 i - 1位的积
            if(!ans.size()) ans.push_back(1);
            else ans.push_back(ans[i - 1] * A[i - 1]);
        }
        int mt = 1;
        for(int i = A.size() - 1; i >= 0; i --){ //加上 i + 1 - > n 积
            if(A.size() - 1 == i) {
                mt = A[i];
                continue;
            }
            ans[i] *= mt;
            mt *= A[i];
        }
        return ans;
    }
};

时间复杂度: $O\left(n\right)O(n)$O(n) 正序遍历一遍逆序遍历一遍最高复杂度为$O\left(n\right)O(n)$O(n)

空间复杂度: $O\left(n\right)O(n)$O(n) 用来存储答案会存入n个元素