剑指offer-构建乘积数组

描述题目：给定一个数组A [0,1，…，N-1]，请构建一个数组B [0,1，…，N-1]，其中乙中的元素B [I ] = A [0] * A [1] * … * A [I-1] * A [1 + 1] * … * A [N-1]。不能使用除法。

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        if(!A.size()) return vector<int>();
        int n = A.size();
        if(n==2)
            return vector<int> {A[1],A[0]};
        vector<int> res(n,0);
        res[0] = A[1];
        res[1] = A[0];
        int multi = A[0] * A[1];
        for(int i=2;i<n;++i) {
            res[i] = multi;
            for(int j=0;j<i;++j){
                res[j] *= A[i];
            }
            multi = res[i] * A[i];
        }
        return res;
    }
};//整体时间复杂度为o(n*n)

• 将问题简化 一开始如果只有两个元素的时候只需要交换原始数组的两个元素的值

• 当第三个元素进来的时候只需要将前面的所有元素乘以当前进来的元素，当前元素的位置值等于前面元素的和乘积。

官方的思路 使用分段的方法

/**
 * 思路：剑指的思路，可以观察B和A的规律
 B0     =  1  A1  A2  ... A(n-1)
 B1     = A0   1  A2  ... A(n-1)
 B2     = A0  A1   1  ... A(n-1)
 ...
 B(n-1) = A0  A1  A2  ... 1

 * 由1连成的对角线把矩阵分成了上三角和下三角，可以根据规律先把下三角算出来，然后再对称得出完整的B

 */
class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        int len = A.size();
        if(len == 0) return A;
        vector<int> B;
        //计算下三角形
        B.push_back(1);
        for(int i = 1; i < len; i++){
            B.push_back(B[i-1] * A[i-1]);
        }
        //合并上三角形
        int temp = 1;
        for(int i = len-2; i >= 0; i--){
            temp *= A[i+1];
            B[i] *= temp;
        }
        return B;
    }
};//这只需要o(n)的时间复杂度明显提升了