题目描述

给定一个数组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]。

样例

输入：[1, 2, 3, 4, 5]

输出：[120, 60, 40, 30, 24]

算法1

(模拟)

1. ，貌似不能用除法。。先暴力做一个，第二种解法是看y总的。
2. 暴力就很简单了，有0就把0删掉存到一个数组中，没0就无脑写。

时间复杂度

$O(n)$

C++ 代码

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> B;
        int mul = 1;
        for(auto x : A)
            mul *= x;

        if(!mul)
        {
            for(auto x : A)
                if(x) B.push_back(x);
                else continue;
        }

        int bm = 1;
        for(auto x : B)
            bm *= x;


        vector<int> C;
        if(!mul)
        {
            for(auto x : A)
                if(x) C.push_back(0);
                else C.push_back(bm);
        }
        else
        {
            for(auto x : A)
                C.push_back(mul / x);
        }

        return C;
    }
};

算法2

(模拟)

1. 分2次求
2. 第一次求i左边的，第二次求i右边的。第1次顺着求，第2次逆着求。
3. 通过这个可以好好体会下 迭代，自己写得很复杂还错，还是太菜了。。

时间复杂度

$O(n)$

C++ 代码

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        int n = A.size();
        if(!n) return vector<int> ();

        vector<int> B(n);
        for(int i = 0, p = 1; i < n; i ++)
        {
            B[i] = p;
            p *= A[i];
        }

        for(int i = n - 1, p = 1; ~i; i --)
        {
            // B[i] = p;
            B[i] *= p;
            p *= A[i];
        }

        return B;
    }
};