leetcode - - - the product of an array other than itself

Title:

Given an integer array of length n, nums, where n > 1, returns the output array, where output[i] equals the product of all elements in nums except nums[i].

Note: You can't use division. In fact, if there is 0 in the array, it's extremely troublesome to use division.

Input: [1, 2, 3, 4]
Output: [24, 12, 8, 6]

I just started thinking that every number must be the product of the left and the right, so as long as we calculate the product sum of the left and the product sum of the right, we can certainly get the total product sum; but I didn't think that I would first traverse the left side, calculate the product sum of the left side of each number, and then traverse from the right side, calculate the product sum of the right side, and then each number. It's the product sum on the left and the product sum on the right.

I thought, unfortunately, I didn't think, I don't know why, so I thought, can we use divide and conquer, every time we multiply and return the left side of each number, and the right side of the product and also return, and then calculate the product of each number and the relative side and the number of products, respectively, as the sum of this number;

So my time complexity is: because every number of k groupings has to be calculated once a time, so it's O (n) +O (n/2) +O (n/4) +.... +1, cumulative sum is 0 (n) +O (n/2) +O (n/4) +.... +1

Therefore, the time complexity is O(n);

class Solution {
public:
    int Fenzhi(vector<int> &nums,vector<int> &copy,int lo,int hi)
    {
        if(lo==hi){
            copy[lo]=1;  //If you calculate this number, it's 1.
            return nums[lo];    //Returns to another number to be calculated
        }
        int mi=lo+(hi-lo)/2;
        int value=1;
        int left=Fenzhi(nums,copy,lo,mi);  //All product sums on the left
        int right=Fenzhi(nums,copy,mi+1,hi); //All product sums on the right
        for(int i=lo;i<=mi;++i)
        {
            copy[i]*=right;        //Calculate the product and sum of each number on the left and all the products on the right.
        }
        for(int i=mi+1;i<=hi;++i)
        {
            copy[i]*=left;        //Calculate the product and sum of each number on the right and all products on the left
        }
        return left*right;

    }
    
    
    
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> copy(nums.size(),1);
        Fenzhi(nums,copy,0,nums.size()-1);
        return copy;
    }
};

The following solution is the code of the left product and the right product I just mentioned.

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        vector<int> v1(n,1),v2(n,1);
        
        for(int i=1;i<n;i++){//Left product
            v1[i]=v1[i-1]*nums[i-1];
        }
        
        for(int i=n-2;i>=0;i--){//Finding right product
            v2[i]=v2[i+1]*nums[i+1];
        }
        
        for(int i=0;i<n;i++){//Left product*right product
            v1[i]*=v2[i];
        }
        
        return v1;
    }
};

The following algorithm optimizes the above code so that the product sum on the left and the product sum on the right are computed separately in one traversal. It uses two pointers to record the product sum before the left and the product sum before the right respectively.

This reduces the time complexity from O(3n) to O(n)

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        
        int n=nums.size();
        int left=1,right=1;     //Left: Multiplication from the left, right: Multiplication from the right
        vector<int> res(n,1);
        
        for(int i=0;i<n;++i)    //Finally, the left and right product of each element is multiplied and the result is obtained.
        {
            res[i]*=left;       //Multiplied by the product on its left
            left*=nums[i];
            
            res[n-1-i]*=right;  //Multiplied by the product on its right
            right*=nums[n-1-i];
        }
        
        return res;
        
    }
};

 

Posted on Mon, 07 Oct 2019 00:43:58 -0700 by adityamenon90