本文共 1256 字，大约阅读时间需要 4 分钟。

题目：给定一个数组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[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2];）

对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在。

解法一：两层循环，内层求累乘，时间复杂度较大

# -*- coding:utf-8 -*-class Solution:    def multiply(self, A):        # write code here        b = []        if len(A) == 1:            return None        for i in range(len(A)):            s = 1            for j in range(len(A)):                if j != i:                    s *= A[j]            b.append(s)        return b

解法二：动态规划思想

对B[i] = A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1] = left[i] * right[i]

left[i] = A[0]*A[1]*...*A[i-1]

right[i] = A[i+1]*...*A[n-1]

left[i+1] = left[i]*A[i]

right[i] = right[i-1]*A[i-1]

left[0] = 1

right[n-1] = 1

这样只需要构建一个新的left和right数组即可降低时间复杂度，但是会增加额外的空间消耗。

# -*- coding:utf-8 -*-class Solution:    def multiply(self, A):        # write code here        left = [1 for i in range(len(A))]        right = [1 for i in range(len(A))]                for i in range(1,len(A)):            left[i] = left[i-1] * A[i-1]            right[len(A)-1-i] = right[len(A)-i] * A[len(A)-i]                    b = []        for i in range(len(A)):            b.append(left[i]*right[i])        return b

转载地址：https://blog.csdn.net/sinat_42437278/article/details/118157347 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！