Author: chengbei public number: front under the mealCopy the code

Output [I] is equal to the product of all the elements in NUMs except nums[I].

Tip: The topic data guarantees that all prefix element and suffix products of any element in the array are in the range of 32-bit integers. Note: Please do not use division and complete this problem in o(n) time

The lowest version is as follows, although the function is realized, but does not meet the requirements, can not use division, division operation is not welcome.

*/ * * * * *@param {number*[] *} nums*
** @return {number*[] *}* * * /*
var productExceptSelf = function(nums) {
    if(! nums || ! nums.length) {throw new Error('Nums must be an array greater than 1.')}var output = new Array(nums.length), total = 1

    for (let index = 0; index < nums.length; index++) {
        total *= nums[index]
    }

    for (let index = 0; index < nums.length; index++) {
        output[index] = total / nums[index]
    }

    return output
};

var output = productExceptSelf([1.2.3.4])
console.log(output)
Copy the code

I thought of another method, two cycles, but the time is so complicated as to be O(n2) that it doesn’t work either

for (let index = 0; index < nums.length; index++) {
    output[index] = 1
    for (let index2 = 0; index2 < nums.length; index2++) {
        if(index ! == index2) { output[index] *= nums[index2] } } }Copy the code

If you think about the lowest version, the main problem is that you use division, is there another way to do it? Can consider twice traversal, respectively from the front and back, from the back forward traversal, calculate the product of precursors, and drive the product after the corresponding index as the product of two multiplied again meet the subject as a result, the time complexity is O (n) meet the requirements, by using the output to store intermediate results, so the space complexity is only O (1), declare a variable result.

var output = new Array(nums.length), result = 1
output[0] = 1

// The output is only multiplied by the precursor
for (let index = 1; index < nums.length; index++) {
    result *= nums[index - 1]
    output[index] = result
}

result = 1
// The output is added to the product of the rear drive
for (let index = nums.length - 2; index >= 0; index--) {
    result *= nums[index + 1]
    output[index] *= result
}
Copy the code