JZOffer-66

剑指 Offer 66. 构建乘积数组

1 题目描述

• 题目链接：剑指 Offer 66. 构建乘积数组

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

示例1：

输入: [1,2,3,4,5]
输出: [120,60,40,30,24]

示例2：

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

2 思路

  最简单的思路就是创建一个变量cnt并初始化为1, 然后再遍历数组，将cnt除去当前遍历的元素即可得到答案数组，但存在一个问题就是可能出现0的情况导致最后乘完cnt=0，最后答案数组就变成了全为0的数组，因而需要额外计算0的个数，当0的个数大于1，则答案数组全为0，而当0个数为0则正常操作，而0的个数恰好为1时则除了为0的位置之外其余均为0.

  然而，题目中要求不能使用除法,因而上边的方法实际上是不可行的。重新理解一下题目，题目中求的是nums数组中除了本身之外其余元素的乘积，那么可以将这个乘积分为左边子数组的乘积与右边子数组的乘积，最后再将两个乘积乘起来就是答案了。如何操作？可以定义两个数组，Left用来存放左边数组的乘积，Right用来存放右边数组的乘积, 这两个数组的构造方法为：

• Left[i] = Left[i-1] * nums[i-1];, 初始化为1，并且下标从1开始.
• Right[i] = Right[i+1] * nums[i+1];, 初始化为1，并且下标从n-2开始.

  最后将两个数组的对应位置相乘就是答案了，即res[i] = Left[i] * Right[i];

class Solution {
public:
    vector<int> constructArr(vector<int>& a) {
        int n = a.size();
        if(n == 0) return a;
        vector<int> Left(n, 1), Right(n, 1);
        // 构造左边子数组乘积
        for(int i = 1; i < n; ++i){
            Left[i] = Left[i-1] * a[i-1];
        }
        // 构造右边子数组乘积
        for(int i = n-2; i >= 0; --i){
            Right[i] = Right[i+1] * a[i+1];
        }
        // 计算结果
        vector<int> res(n);
        for(int i = 0; i < n; ++i){
            res[i] = Left[i]*Right[i];
        }
        return res;
    }
};

  进一步的，似乎没有必要构造这么多数组，直接将Left数组作为答案数组，然后在求右边乘积的时候，用一个变量来存储即可，从而降低了空间复杂度(只是将空间复杂度从O(3N)变为O(N)).

class Solution {
public:
    vector<int> constructArr(vector<int>& a) {
        int n = a.size();
        vector<int> res(n, 1);
        // 这里其实就是左边乘积
        for(int i = 1; i < n; ++i){
            res[i] = res[i-1] * a[i-1]; 
        }
        // 这里是求右边乘积并更新答案
        int tmp = 1;    // tmp用于存放右边子数组乘积结果
        for(int i = n-2; i >= 0; --i){
            tmp *= a[i+1];
            res[i] *= tmp;
        }
        return res;
    }
};

  更进一步的，上边的解法需要两次遍历,但实际上我们可以用两个变量，Left存储左边乘积，Right存储右边乘积,然后在遍历过程中从两端对答案数组进行更新。

class Solution {
public:
    vector<int> constructArr(vector<int>& a) {
        int n = a.size();
        vector<int> res(n, 1);
        int Left = 1, Right = 1;
        for(int i = 0; i < n; ++i){
            res[i] *= Left;         // 先乘左乘积
            res[n-1-i] *= Right;    // 最后回过头再乘上右乘积
            Left *= a[i];           // 左边乘积
            Right *= a[n-i-1];      // 右边乘积
        }
        return res;
    }
};