题目描述
给定一个数组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]。不能使用除法。
题目地址
思路
观察下公式,你会发现,B[i]公式中没有A[i]项,也就是说如果可以使用除法,就可以用公式B[i]=A[0]*A[1]*.....*A[n-1]/A[i]来计算B[i],但是题目要求不能使用,因此我们只能另想办法。
思路1:遍历数组,每次与除i的元素相乘,时间复杂度为O(n^2)
思路2:更高效的算法。可以把B[i]=A[0]*A[1]*.....*A[i-1]*A[i+1]*.....*A[n-1]。看成A[0]*A[1]*.....*A[i-1]和A[i+1]*.....A[n-2]*A[n-1]两部分的乘积。
即通过A[i]项将B[i]分为两部分的乘积。效果如下图所示:
不妨设定C[i]=A[0]*A[1]*...*A[i-1],D[i]=A[i+1]*...*A[n-2]*A[n-1]。C[i]可以用自上而下的顺序计算出来,即C[i]=C[i-1]*A[i-1]。类似的,D[i]可以用自下而上的顺序计算出来,即D[i]=D[i+1]*A[i+1]。
如果还是不明白,没有关系,直接看下代码,细细体会下就懂了。
第一个for循环用来计算上图1范围的数,第二个for循环用来计算上图2范围的数。
Python
# -*- coding:utf-8 -*-
class Solution:
def multiply(self, A):
# write code here
if len(A) <= 0:
return []
# 思路1:
# B = []
# for i in range(len(A)):
# temp = 1
# for j in range(len(A)):
# if j != i:
# temp *= A[j]
# B.append(temp)
# return B
# 思路2:
B = [1]*len(A)
for i in range(1,len(A)):
B[i] = B[i-1]*A[i-1]
temp = 1
for i in range(len(A)-2,-1,-1):
temp *= A[i+1]
B[i] *= temp
return B if __name__ == '__main__':
result = Solution().multiply([0,1,2,3,4])
print(result)