剑指offer-构建乘积数组

本文为剑指 offer 系列第四十八篇。
主要知识点为数组，但是可以通过类似于矩阵的方式来进行性能的提升。

题目描述

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

其实我们在计算的时候可以发现很多计算是重复的，举例来说
1, 2, 3, 4, 5
计算第一个数字的时候是2*3*4*5,
计算第二个数字的时候是1*3*4*5,
计算第三个数字的时候是1*2*4*5,
计算第四个数字的时候是1*2*3*5,
计算第五个数字的时候是1*2*3*4。
这样就可以发现很多运算是重复的，比如第一行的345和第二行的345，
如何去掉重复的计算呢？就是我们接下来要考虑的问题。
同样以1, 2, 3, 4, 5为例来进行说明，我们可以发现同一行的计算可以分成左右两个部分。
计算第一个数字的时候是(1)*(2*3*4*5),
计算第二个数字的时候是(1*1)*(3*4*5),
计算第三个数字的时候是(1*2*1)*(4*5),
计算第四个数字的时候是(1*2*3*1)*(5),
计算第五个数字的时候是(1*2*3*4*1)()。
左面括号中下一行的数字是上一行的数字再乘上一个数字，
右面括号中上一行的数字是下一行的数组再乘上一个数字。
而最终的结果就是左边的括号乘上右面的括号。
非常优秀的思路。

解题代码

思路1代码

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        //  方法1: 双层遍历 O(n^2)
        vector<int> res ;
        int temp = 1;
        for(int i  = 0;i< A.size();i++){
            for(int j = 0; j< A.size(); j++){
                if(i != j){
                   temp = A[j] *temp;
                }
            }
            res.push_back(temp);
            temp = 1;
        }
        return res;
    }
};

时间复杂度为O(n^2),空间复杂度为O(n)

思路2代码

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        //  方法2: 巧妙运用一下前一次和后一次的关系
        vector<int> res;
        vector<int> left = {1};
        vector<int> right = {1};
        for(int i = 1; i <= A.size()-1; i++){
            left.push_back(left.back()* A[i-1]);
        }
        for( int i = A.size()-2; i>=0;i--){
            right.insert(right.begin(),right.front()*A[i+1]);
        }
        for(int i = 0; i<A.size();i++){
            res.push_back(left[i] * right[i]);
        }
        return res;
    }
};

时间复杂度为O(n),空间复杂度为O(n)
以上，本题结束！