238. Product of Array Except Self
題目:
https://leetcode.com/problems/product-of-array-except-self/
難度:
Medium
不使用division 并且O(n)
想到的算法 O(n^2)
會(huì)超時(shí)
class Solution(object):
def productExceptSelf(self,nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
lst = []
for i in range(len(nums)):
lst.append(self.productWithoutI(nums,i))
return lst
def productWithoutI(self,nums,i):
product = 1
for j in range(len(nums)):
if j != i:
product *= nums[j]
return product
如果用除法泞边，也會(huì)有問題，如果有0出現(xiàn)也會(huì)變繁瑣点寥。
谷歌一下：
解法還是很棒的
output[i] = { i 前面的數(shù)的乘積} X { i 后面的數(shù)的乘積}
class Solution(object):
def productExceptSelf(self,nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
if nums == [] : return []
lft = [1]
rgt = [1]
product = 1
for i in range(1,len(nums)):
product *= nums[i-1]
lft.append(product)
product = 1
for i in reversed(range(1,len(nums))):
product *= nums[i]
rgt.append(product)
rgt.reverse()
result = []
for i in range(len(nums)):
result.append(lft[i]*rgt[i])
return result
空間O（n），再看到滿足要求的“標(biāo)準(zhǔn)解法”
class Solution(object):
def productExceptSelf(self,nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
if nums == [] : return []
size = len(nums)
output = [1] * size
left = 1
for x in range(size-1):
left *= nums[x]
output[x+1] *= left
right = 1
for x in range(size - 1, 0, -1):
right *= nums[x]
output[x-1] *= right
return output
