当前位置：网站首页>leetcode：238. Product of arrays other than itself

leetcode：238. Product of arrays other than itself

2022-06-29 20:56:00 【Oceanstar's learning notes】

Title source

leetcode：238. The product of an array other than itself

title

Insert picture description here

The prefix and

According to the meaning , For each $a n s [i]$ Both consist of two parts ：
$(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])$

therefore , We can use the idea of prefix and , Request two arrays $s 1 [?], s 2 [?]$ （ hypothesis n = nums.size()）

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

After processing ： $a n s [i] = s 1 [i] * s 2 [i]$

Insert picture description here

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]  Index  i  The product of all the elements on the left 
        s1[0] = 1;
        for (int i = 1; i < m; ++i) {
    
            s1[i] = s1[i - 1] * nums[i - 1];
        }

        // s2[i]  Index  i  The product of all elements on the right 
        s2[m - 1] = 1;
        for (int i = m - 2; i >= 0; --i) {
    
            s2[i] = s2[i + 1] * nums[i + 1];
        }

        //  For index  i, except  nums[i]  The product of other elements is the product of all elements on the left multiplied by the product of all elements on the right 
        vector<int> ans(m, 0);
        for (int i = 0; i < m; ++i) {
    
            ans[i] = s1[i] * s2[i];
        }
        return ans;
    }
};

Insert picture description here

Spatial complexity O(1)O(1) Methods

Because the output array is not included in the space complexity , Then we can L or R Arrays are computed using output arrays . First treat the output array as L Array to calculate , And then dynamically construct R Array gets the result .

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;
    }
};