构建乘积数组

给定一个数组 $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长度为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 (n^{2})$ 对于每一位会遍历n次所以总复杂度为 $O (n^{2})$

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

方法二: 前缀后缀乘积

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

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 (n)$ 正序遍历一遍逆序遍历一遍最高复杂度为 $O (n)$

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

题解 | #构建乘积数组#

构建乘积数组

方法一: 暴力

方法二: 前缀后缀乘积