剑指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)。
左面括号中的乘积可以从上一行算出来，右面括号中的乘积则可以从下一行算出来，各自只要再乘上一个数字。
而最终的结果就是左边的括号乘上右面的括号。
非常优秀的思路。

解题代码

思路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(size_t i = 1; i < A.size(); i++){
            left.push_back(left.back()* A[i-1]);
        }
        for(size_t i = A.size(); i > 1; 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^2)，空间复杂度为O(n)。虽然前后乘积避免了重复乘法，但是right每次向vector头部插入，仍需要移动已有元素。
以上，本题结束！