“This is the 14th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Note: Part of the article content and pictures from the network, if there is infringement please contact me (homepage public number: small siege lion learning front)

By: Little front-end siege lion, home page: little front-end siege lion home page, source: Nuggets

GitHub: P-J27, CSDN: PJ wants to be a front-end siege lion

Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.

The question to describe

You are given an array of integers of length n, nums, where n > 1 returns output, where output[I] is equal to the product of all elements in nums except nums[I].

Example:

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

Tip: The problem data ensures that the product of all prefixes and suffixes (or even the entire array) of any element in the array is within the range of 32-bit integers.

Note: Do not use division and complete this problem in O(n) time complexity.

Advanced: Complete the problem within constant space complexity, and the output array is not treated as extra space.

Solution one: prefix product & suffix product

Description:

  • Prefix product: the product storing the first element to itself (excluding itself)
  • 1. The product of the last element stored to itself (excluding itself).

Analysis: the product of all the elements to the left of any position multiplied by all the elements to the right of the position, then the product of prefixes * the product of suffixes is what we want.

var productExceptSelf = function(nums) {
    if(! nums.length)return [];
    if (nums.length === 1) return [1];

    const len = nums.length;
    let l = new Array(len),
        r = new Array(len),
        ret = [];

    l[0] = 1;
    for (let i = 1; i < len; ++i) {
        l[i] = nums[i - 1] * l[i - 1];
    }
    r[len - 1] = 1;
    for (let i = len - 2; i >= 0; --i) {
        r[i] = nums[i + 1] * r[i + 1];
    }
    l.forEach((val, idx, arr) = > {
        ret.push(val * r[idx]);
    });
    return ret;
};
Copy the code

Solution two (constant space) : prefix product & rolling suffix product constant

  • Only prefix accumulative groups are built.
  • When calculating the result, a rolling variable is used to maintain the desired postfix product constant.
  • Or the other way around, just an array, just a constant
const productExceptSelf = nums= > {
    const len = nums.length;
    // Define the left cumulative array with the initial value 1
    const resLeft = new Array(len).fill(1);
    for (let i = 1; i < len; i++) {
        // Start with I =1 and run the left cumulative operation
        resLeft[i] = resLeft[i - 1] * nums[i - 1];
    }
    let Right = 1;
    for (let i = len - 1; i >= 0; i--) {
        resLeft[i] = resLeft[i] * Right;
        Right *= nums[i];
    }
    return resLeft;
};
Copy the code

Thank you for reading, I hope to help you, if there is a mistake or infringement of the article, you can leave a message in the comment area or add a public number in my home page to contact me.

Writing is not easy, if you feel good, you can “like” + “comment” thanks for your support ❤