解法1, 用一个list记录从左边开始除了自己的乘积,然后另一个list记录右边开始除了自己的乘积,然后把这辆list对应项乘起来就行。实际实现的时候右边的list可以用一个数代替节省一点空间
例子 1,没有0的情况
例子 2,有0的情况
思路其实和盛水题目有点像
时间 O(N),空间 O(N)
Python代码
class Solution:
# @param {integer[]} nums
# @return {integer[]}
def productExceptSelf(self, nums):
l = len(nums)
ret = [1] * l
for i in range(1, l):
ret[i] = ret[i-1] * nums[i-1]
right = 1
for i in range(l-2, -1, -1):
right *= nums[i+1]
ret[i] *= right
return ret
解法2,根据0的情况分类。
如果没0,全部乘起来,然后再扫一遍,除以自己。
有一个0,把非0的乘起来,除了0的位置,其他全是0, 0的位置为其他非0的乘积。
有2个及以上的0,全部都是0
例子
时间 O(N),空间 O(N)
Python
class Solution(object):
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
product = None
zero_index = None
zero_counts = 0
for i in xrange(len(nums)):
if product is None:
product = nums[i]
continue
if nums[i] != 0:
product *= nums[i]
else:
zero_counts += 1
zero_index = i
if zero_counts == 2:
break
if product is None:
return product
if zero_counts == 0:
products = [product / x for x in nums]
elif zero_counts == 1:
products = [0] * len(nums)
products[zero_index] = product
else:
products = [0] * len(nums)
return products
做这题想到这俩解法相隔竟已5年。