【LeetCode-数组】除自身以外数组的乘积

题目描述

给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例：

输入: [1,2,3,4]
输出: [24,12,8,6]

提示： 题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。

说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。

进阶：
你可以在常数空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
题目链接： https://leetcode-cn.com/problems/product-of-array-except-self/

思路1

最初始的方法：使用两层循环，外层循环遍历数组，内层循环计算数组除了当前数字之外其他数字的乘积。但这种方法的时间复杂度为 O(n^2)，不符合题目要求，而且会超时。代码如下：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        if(nums.empty()) return {};

        vector<int> ans;
        for(int i=0; i<nums.size(); i++){
            int t = 1;
            for(int j=0; j<i; j++) t *= nums[j];
            for(int k=i+1; k<nums.size(); k++) t *= nums[k];
            ans.push_back(t);
        }
        return ans;
    }
};
// 超时

时间复杂度：O(n^2)
空间复杂度：O(1)

思路2

不包含第 i 个元素的乘积 = 第 i 个元素左边的乘积 * 第 i 个元素右边的乘积。我们使用 left[i] 表示第 i 个元素左边的乘积，使用 right[i] 表示第 i 个元素右边的乘积。提前计算好 left[i] 和 right[i]。对于 left 数组，将元素全部初始化为 1，有

left[0] = 1;
left[i] = left[i-1] * nums[i-1];

同样地，对于 right 数组，将元素全部初始化为 1，有

right[nums.size()-1] = 1;
right[i] = right[i+1] * nums[i+1];

不包含第 i 个元素的乘积 = left[i] * right[i]. 代码如下：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        if(nums.empty()) return {};

        vector<int> left(nums.size(), 1);
        vector<int> right(nums.size(), 1);

        for(int i=1; i<nums.size(); i++) left[i] = nums[i-1] * left[i-1];
        for(int i=nums.size()-2; i>=0; i--) right[i] = nums[i+1] * right[i+1];

        vector<int> ans;
        for(int i=0; i<nums.size(); i++){
            ans.push_back(left[i]*right[i]);
        }
        return ans;
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

思路3

还可以对思路 2 的空间复杂度进一步优化。我们使用 ans 数组替代 left 数组，首先使用计算 left 数组的方式计算 ans 数组，计算完成后 ans[i] 就是第 i 个元素之前的元素乘积，然后将变量 r 设为数组倒数第一个元素，也就是 r = nums[nums.size()-1]，然后从倒数第二个元素开始往前遍历，遍历过程中 ans[i] = ans[i] * r; r = r * nums[i]，r 就代替了 right 数组。代码如下：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        if(nums.empty()) return {};

        vector<int> ans(nums.size(), 1);
        for(int i=1; i<nums.size(); i++) ans[i] = ans[i-1] * nums[i-1];

        int r = nums[nums.size()-1];
        for(int i=nums.size()-2; i>=0; i--){
            ans[i] *= r;
            r *= nums[i];
        }
        return ans;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)