Product of Array Except Self
Given an array of n integers where n > 1, nums
, return an array output
such that output[i]
is equal to the product of all the elements of nums
except nums[i]
.
Solve it without division and in O(n).
For example, given [1,2,3,4]
, return [24,12,8,6]
.
Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
https://leetcode.com/problems/product-of-array-except-self/
去掉限制条件的话非常水。
但是题目要求不能用除法,线性时间复杂度,常数的空间复杂度,这也不行那也不行真是任性。
解法是构造两个数组,第一轮遍历累乘左边的值,第二轮遍历累乘右边的值。
比如:[3, 4, 5, 6]
累乘左,第一个是1:[1, 3, 3*4, 3*4*5]
累乘右,最后一个是1:[4*5*6, 5*6, 6, 1]
这两个数组再相乘就是结果。
1 /** 2 * @param {number[]} nums 3 * @return {number[]} 4 */ 5 var productExceptSelf = function(nums) { 6 var i, tmp = 1, leftProduct = [], rightProduct = []; 7 leftProduct[0] = 1; 8 for(i = 1; i < nums.length; i++){ 9 leftProduct[i] = nums[i - 1] * tmp; 10 tmp = leftProduct[i]; 11 } 12 rightProduct[nums.length - 1] = 1; 13 tmp = 1; 14 for(i = nums.length - 2; i >= 0; i--){ 15 rightProduct[i] = nums[i + 1] * tmp; 16 tmp = rightProduct[i]; 17 } 18 19 for(i = 0; i < nums.length; i++){ 20 leftProduct[i] = leftProduct[i] * rightProduct[i]; 21 } 22 return leftProduct; 23 };