LeetCode 238 Product of Array Except Self

LeetCode

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

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]

Constraints:

2 <= nums.length <= 10<sup>5</sup> -30 <= nums[i] <= 30
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Follow up: Can you solve the problem in O(1)extra space complexity? (The output array *does not count as extra space for space complexity analysis.)

题目大意：

求每个数对应的结果： 数组出自己外全部相乘

解题思路：

累计思想

解题步骤：

N/A

注意事项：

1. 两轮计算，从左到右，再从右到左，用res数组作为临时计算结果。从左到右，计算res[i] = num[0] x nums[i - 1], 从右到左类似
2. res初始值为1，因为从左到右是跳过第0个值的，而从右到左中res[i] *= product，若初始为0，结果res[i] = 0

Python代码：

def productExceptSelf(self, nums: List[int]) -> List[int]:
	n = len(nums)
	res, product = [1] * n, nums[0]
	for i in range(1, n):
		res[i] = product # [1, 1]
		product *= nums[i]
	product = nums[-1] # 2
	for i in range(n - 2, -1, -1):
		res[i] *= product # [2, 1]
		product *= nums[i]
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(1)

---

若可以用除法算法II解题思路：

按照定义用数学方法，但只要注意一个0和两个0的情况

Python代码：

def productExceptSelf(self, nums: List[int]) -> List[int]:
	product, zero_count = 1, 0
	for n in nums:
		if n != 0:
			product *= n
		else:
			zero_count += 1
	if zero_count > 1:
		return [0] * len(nums)
	res = []
	for i in range(len(nums)):
		if nums[i] == 0:
			res.append(product)
		elif zero_count > 0:
			res.append(0)
		else:
			res.append(int(product / nums[i]))
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(1)