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

发表于： 分类于：
字数： 879 阅读：≈ 2分钟

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

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

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

思路

基本思想

为了计算除自身以外的乘积且不能使用除法，所以需要想出其他的办法，可以看出，当前位置的结果与两侧的乘积有关，我们只需要将两侧的乘积分别统计出来记录到L和R中，最后当前位置i的结果等于L[i]*R[i]，统计时需要注意，统计L时，L[i]=L[i-1]*nums[i]，所以需要注意最左边的情况，同理统计R时需要注意最右边的情况

统计出两个辅助数组之后，就可以再经过一次统计得到最终的结果

上面的方法时间复杂度和空间复杂度都是O(N)，为了进一步减小空间复杂度，可以使用结果容器保存L或者R的内容，然后使用一个变量统计另外一个的内容，从而减小空间复杂度

不管如何L[i]代表第i个元素的左边的所有元素的乘积，包含第i个元素，R[i]同理

执行流程

  1. 统计当前元素的两边的元素乘积
  2. 计算除本身的其余元素乘积
  3. 返回结果

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
    //不能使用除法，否则直接将整体乘积求出来，之后除以每一个元素
    //且只能一次遍历 
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> res(nums.size(),1);
        //res[i]代表第i个位置的右边所有元素乘积，包含第i个元素
        res[nums.size()-1]=nums[nums.size()-1];
        //使用res保存右边的乘积结果
        for(int i=nums.size()-2;i>=0;--i){
            res[i]=nums[i]*res[i+1];
        }
        int L=1;
        for(int i=0;i<nums.size();++i){
            if(i==0){
                res[i]=res[i+1];
                L=L*nums[i];
            }
            else if(i==nums.size()-1)
                res[i]=L;
            else{
                res[i]=res[i+1]*L;
                L=L*nums[i];
            }
        }
        return res;
    }
};

总结

善于将问题拆分，从而当前元素的结果等于左右所有元素的乘积，所以需要将左右元素的乘积求出来，用两个容器存储这些辅助元素，进一步为了减小空间复杂度，从而可以使用结果容器保存左边或者右边的辅助元素，从而另一边的辅助元素需要使用一个变量存储

当结果容器存放的是左边的辅助元素，那么就需要从尾部进行更新，从头更新会将辅助元素覆盖，当结果容器存放的是右边的辅助元素，那么就需要从头开始更新

核心就是当前元素的结果等于左右两边的元素乘积，之后结果容器保存辅助元素时，不能将没用过的辅助元素覆盖