238. 除自身以外数组的乘积

刷题记录
留言

238. 除自身以外数组的乘积

题目

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

示例:

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

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

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

进阶：
你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

主要思路

首先应该想到的是使用两个数组，分别存放左乘结果和右乘结果，这样最后两个数组中相同位置的乘积即为除该处元素外的乘积。这是一种$O(n)$的解法

为了保证常数空间复杂度，就需要想办法对空间进行优化。由于输出数组不被视为额外空间，那么我们就可以将输出数组先作为单边乘积数组。

然后另一边乘积数组我们发现其实每次计算只和前一个元素有关系，所以我们使用一个变量来代表。但同时这也意味着我们最终计算时的方向已经确定了。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        // 要求用额外常数级空间 但不计入答案数组
        // 所以想办法使用答案数组。
        vector<int> ans(nums.size());
        // 此处计算的答案数组是左乘结果数组
        ans[0]=1;
        for(int i=1;i<nums.size();i++){
            ans[i] = ans[i-1]*nums[i-1];
        }
        // 本来应该有一个右乘结果数组，但为了空间，只能优化掉，用一个变量代表当前右乘结果
        int R = 1;
        // 因为右乘结果不断变化，所以我们从右边算起
        for(int i=nums.size()-1;i>=0;i--){
            ans[i] = ans[i]*R;
            R = R*nums[i];
        }
        return ans;
    }
};