Leetcode[238] Product of Array Except Self
29 Nov 2015###Task1 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].
###Python ####O(n) space
class Solution(object):
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
N = len(nums)
left = [1 for i in range(N)]
right = [1 for i in range(N)]
cur = nums[0]
for i in range(1, N):
left[i] = cur
cur *= nums[i]
cur = nums[-1]
for i in range(1, N):
right[-1 - i] = cur
cur *= nums[-1 - i]
ret = []
for i in range(N):
ret.append(left[i] * right[i])
return ret
####O(1) space
class Solution(object):
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
N = len(nums)
ret = [1 for i in range(N)]
left = nums[0]
for i in range(1, N):
ret[i] *= left
left *= nums[i]
right = nums[-1]
for i in range(1, N):
ret[-1 - i] *= right
right *= nums[-1 - i]
return ret
###Java
public class Solution {
public int[] productExceptSelf(int[] nums) {
if (nums == null || nums.length == 0) {
return null;
}
int[] res = new int[nums.length];
int[] left = new int[nums.length];
int[] right = new int[nums.length];
left[0] = 1;
for (int i = 1; i < nums.length; i++) {
left[i] = left[i - 1] * nums[i - 1];
}
right[nums.length - 1] = 1;
for (int i = nums.length - 2; i >= 0; i--) {
right[i] = right[i + 1] * nums[i + 1];
}
for (int i = 0; i < nums.length; i++) {
res[i] = left[i] * right[i];
}
return res;
}
}