原题
给定一个整数数组A。
定义B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]， 计算B的时候请不要使用除法。
样例
给出A=[1, 2, 3]，返回 B为[6, 3, 2]
解题思路
- 求出数组中每一个位置左边的乘积和右边的乘积
- 最后遍历每一个位置，把左右乘积相乘
- 时间复杂度O(n) - 扫两遍，或者可以扫三遍
完整代码
class Solution(object):
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
p = 1
n = len(nums)
output = []
for i in range(0,n):
output.append(p)
p = p * nums[i]
p = 1
for i in range(n-1,-1,-1):
output[i] = output[i] * p
p = p * nums[i]
return output
