当前位置：网站首页>leetcode：238. 除自身以外数组的乘积

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

2022-06-29 20:51:00 【OceanStar的学习笔记】

题目来源

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

题目解析

在这里插入图片描述

前缀和

根据题意，对于每个 $a n s [i]$ 均由两部分组成：
$(n u m s [0] \times n u m s [1] \times . . . \times n u m s [i - 1]) \times (n u m s [i + 1] \times n u m s [i + 2] \times . . . \times n u m s [n - 1])$

所以，我们可以用前缀和的思想，申请两个数组 $s 1 [?] ， s 2 [?]$ （假设n = nums.size()）

$s 1 [i] = n u m [0 . . . . . i - 1]$
$s 2 [i] = n u m [i + 1 . . . . n - 1]$

处理完成之后： $a n s [i] = s 1 [i] * s 2 [i]$

在这里插入图片描述

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

        int m = nums.size();

       
        std::vector<int> s1(m, 0), s2(m, 0);
        
        // s1[i] 为索引 i 左侧所有元素的乘积
        s1[0] = 1;
        for (int i = 1; i < m; ++i) {
    
            s1[i] = s1[i - 1] * nums[i - 1];
        }

        // s2[i] 为索引 i 右侧所有元素的乘积
        s2[m - 1] = 1;
        for (int i = m - 2; i >= 0; --i) {
    
            s2[i] = s2[i + 1] * nums[i + 1];
        }

        // 对于索引 i，除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积
        vector<int> ans(m, 0);
        for (int i = 0; i < m; ++i) {
    
            ans[i] = s1[i] * s2[i];
        }
        return ans;
    }
};

在这里插入图片描述

空间复杂度 O(1)O(1) 的方法

由于输出数组不算在空间复杂度内，那么我们可以将 L 或 R 数组用输出数组来计算。先把输出数组当作 L 数组来计算，然后再动态构造 R 数组得到结果。

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

        int m = nums.size();
        int pre = 0, front = 0;
       
        vector<int> ans(m, 1);

        pre = 1;
        ans[0] *= pre;
        for (int i = 1; i < m; ++i) {
    
            pre = pre * nums[i - 1];
            ans[i] *= pre;
        }
        

        front = 1;
        ans[m - 1] *= front;
        for (int i = m - 2; i >= 0; --i) {
    
            front = front * nums[i + 1];
            ans[i] *= front;
        }

        
        return ans;
    }
};