题目描述:给定一个数组 $A[0,1,…,n-1]$, 请构建一个数组 $B[0,1,…,n-1]$, 其中 $B$ 中的元素 $B[i]=A[0]A[1]…A[i-1]A[i+1]…A[n-1]$。不能使用除法。
Solutions
如果采用暴力方法的话需要 $O(n^2)$,这里采用费空间换时间的方式,将连乘从断开的部分分成两个部分,分别用两个向量计算。
# -*- coding:utf-8 -*-
class Solution:
def multiply(self, A):
# write code here
n = len(A)
C = [1] * n
D = [1] * n
B = [1] * n
for i in range(1, n):
C[i] = C[i-1] * A[i-1]
for i in range(n-2, -1, -1):
D[i] = D[i+1] * A[i+1]
for i in range(0, n):
B[i] = C[i] * D[i]
return B
# 运行时间:38ms
# 占用内存:5868k
还有优化的一个版本:
# -*- coding:utf-8 -*-
class Solution:
def multiply(self, A):
# write code here
B=[1]*len(A)
for i in range(1,len(A)):
B[i]=B[i-1]*A[i-1]
tmp=1
for j in range(len(A)-2,-1,-1):
tmp *= A[j+1]
B[j]*= tmp
return B
# 运行时间:37ms
# 占用内存:5624k