Leetcode skimming -- no.238 -- product of arrays other than itself

Original link

One 、 Title Description

Give you an array of integers nums, return Array answer , among answer[i] be equal to nums Middle Division nums[i] Product of other elements .
Subject data Guarantee Array nums The product of all prefix elements and suffixes of any element in 32 position In the range of integers .
Please do not use division , And in O(n) Complete this question in time complexity .

Example ：
Example 1:

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

Example 2:

Input : nums = [-1,1,0,-3,3]
Output : [0,0,9,0,0]

Advanced ： You can O(1) Do you complete this problem within the additional spatial complexity of ？（ For the purpose of spatial complexity analysis , Output arrays are not treated as extra space .）

Two 、 Thought analysis

Product left and right list
1） Create two sizes with nums Same array l and r ,l[i] representative i The product of all numbers on the left ,r[i] representative i Product of all numbers on the right .
2） Fill two arrays , Yes l Yes ：l[i] = l[i - 1] * nums[i - 1]; Here we should pay attention to setting the leftmost number to 1：l[0] = 1; Yes r Yes ：r[i] = r[i + 1] * nums[i + 1]; Here we should pay attention to setting the rightmost number to 1：r[numsSize - 1] = 1;
3） Finally, the value of each position is ：r[i] * l[i];

Pictured ：

The same is true for the right side

3、 ... and 、 Code

/** * Note: The returned array must be malloced, assume caller calls free(). */
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
    
    int* l = (int*)malloc(sizeof(int) * numsSize);
    int* r = (int*)malloc(sizeof(int) * numsSize);
    l[0] = 1;
    r[numsSize - 1] = 1;
    for (int i = 1; i < numsSize; i++)
    {
    
        l[i] = l[i - 1] * nums[i - 1];
    }
    for (int i = numsSize - 2; i >= 0; i--)
    {
    
        r[i] = r[i + 1] * nums[i + 1];
    }
    for (int i = 0; i < numsSize; i++)
    {
    
        r[i] *= l[i];
    }
    *returnSize = numsSize;
    return r;
}

Four 、 Advanced

Although the above method solves the problem , However, the spatial complexity is not O(1). by O(N)（nums Size ）
Here's a point ： The output array is not included in the space complexity .
So we just need to create l Array , Create a variable directly from right to left R Instead of ,R Multiplicative multiplication nums The numerical ：

/** * Note: The returned array must be malloced, assume caller calls free(). */
int* productExceptSelf(int* nums, int numsSize, int* returnSize){
    
    int* l = (int*)malloc(sizeof(int) * numsSize);
    l[0] = 1;
    for(int i = 1; i < numsSize; i++)
    {
    
        l[i] = l[i - 1] * nums[i - 1];
    }
    int R = 1;
    for(int i = numsSize - 2; i >= 0; i--)
    {
    
        R *= nums[i + 1];
        l[i] *= R;
    }
    *returnSize = numsSize;
    return l;
}

---

---