052. 构建乘积数组

　　题目描述：给定一个数组 $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

Solutions

References