Leetcode 238 product of arrays other than itself

 

Reference link :https://leetcode-cn.com/problems/product-of-array-except-self/solution/chu-zi-shen-yi-wai-shu-zu-de-cheng-ji-by-leetcode-/

Their thinking : Use the product of all numbers on the left of the index and the product of all numbers on the right ( Prefixes and suffixes ) Multiply to solve .

My solution :

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        // Solution 1 :
        int size=nums.size();
        vector<int>result(size);

        for(int i=0;i<size;i++)
        {
            int L=1;
            int R=1;
             for(int j=0;j<i;++j)
            {
                L*=nums[j];
            }
            for(int k=i+1;k<size;++k)
            {
                R*=nums[k];
            }
            result[i]=L*R;
        }
        return result;
    }
};

There was a problem with the submission : Time limit exceeded

There is also a compilation error problem :

Runtime Error
Line 924: Char 9: runtime error: reference binding to null pointer of type 'int' (stl_vector.h)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/bits/stl_vector.h:933:9

as a result of : vector<int>result(size); Error initializing to vector<int>result( ); The correct form is vector<int>result(size);

LeetCode Solution on the official website :

Method 1 : Is build 3 An array ,L,R,answer

Algorithm :

1. Initialize two empty arrays L and R. For a given index i,L[i] It stands for i The product of all numbers on the left ,R[i] It stands for i The product of all numbers on the right .
2. We need to fill in two loops L and R The value of the array . For arrays L,L[0] Should be 1, Because there is no element to the left of the first element . For other elements ：L[i] = L[i-1] * nums[i-1].
3. Empathy , For arrays R,R[length-1] Should be 1.length Refers to the size of the input array . Other elements ：R[i] = R[i+1] * nums[i+1].
4. When R and L Array fill complete , We just need to iterate over the input array , And index i The value at is ：L[i] * R[i]

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int length = nums.size();

        // L  and  R  Represents the product list on the left and right sides respectively 
        vector<int> L(length, 0), R(length, 0);

        vector<int> answer(length);

        // L[i]  Index  i  The product of all the elements on the left 
        //  For the index is  '0'  The elements of , Because there is no element on the left , therefore  L[0] = 1
        L[0] = 1;
        for (int i = 1; i < length; i++) {
            L[i] = nums[i - 1] * L[i - 1];
        }

        // R[i]  Index  i  The product of all elements on the right 
        //  For the index is  'length-1'  The elements of , Because there is no element on the right , therefore  R[length-1] = 1
        R[length - 1] = 1;
        for (int i = length - 2; i >= 0; i--) {
            R[i] = nums[i + 1] * R[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 
        for (int i = 0; i < length; i++) {
            answer[i] = L[i] * R[i];
        }

        return answer;
    }
};

Method 2 ： Spatial complexity  O(1) Methods

Ideas

Although the above method has been able to solve this problem well , But the spatial complexity is not constant .

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 . Let's look at the algorithm based on this idea .

Algorithm

1. initialization answer Array , For a given index i,answer[i] It stands for i The product of all numbers on the left .
2. The construction method is the same as before , We're just trying to save space , The first answer As method one L Array .
3. The only change in this approach is that we don't construct R Array . Instead, a pass is used to track the product of the elements on the right . And update the array answer[i]=answer[i]*Ranswer[i]=answer[i]∗R. then RR Updated to R=R*nums[i]R=R∗nums[i], Among variables RR It is the product of the number on the right side of the index .

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int length = nums.size();
        vector<int> answer(length);

        // answer[i]  Index representation  i  The product of all the elements on the left 
        //  Because the index is  '0'  There is no element on the left side of the element ,  therefore  answer[0] = 1
        answer[0] = 1;
        for (int i = 1; i < length; i++) {
            answer[i] = nums[i - 1] * answer[i - 1];
        }

        // R  Is the product of all the elements on the right 
        //  At first, there were no elements on the right , therefore  R = 1
        int R = 1;
        for (int i = length - 1; i >= 0; i--) {
            //  For index  i, The product on the left is  answer[i], The product on the right is  R
            answer[i] = answer[i] * R;
            // R  You need to include all the products on the right , So when you calculate the next result, you need to multiply the current value by  R  On 
            R *= nums[i];
        }
        return answer;
    }
};