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

References

  1. 052. 构建乘积数组
  2. 题目:构建乘积数组