面66-构建乘积数组.md

给定一个数组 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]看做C[i] = A[0]×A[1]×…×A[i-1]和D[i] = A[i+1]×…×A[n-1]两部分的乘积,那么就可以先计算出这个两部分的在做乘积就可以了 在接着看下C[i]的求解我们可以使用循环暴力求解,那是O(n^2)的复杂度,但是可以分析出来 $C[i] = C[i-1]*A[i-1]$ D[i]同样可以写出递推式为$D[i] = D[i+1]*A[i+1]$

class Solution(object):
    def constructArr(self, a):
        """
        :type a: List[int]
        :rtype: List[int]
        """
        length = len(a)
        C = [1] * length
        D = [1] * length
        result = []
        for i in range(1,length):#求C[i]
            C[i] = C[i-1] * a[i-1]
        for i in reversed(range(length-1)):#D[i]倒叙
            D[i] = D[i+1] * a[i+1]
        for i in range(length):#求B[i]
            result.append(C[i]*D[i])
        return result

简化一下

class Solution(object):
    def constructArr(self, a):
        """
        :type a: List[int]
        :rtype: List[int]
        """
        length = len(a)
        result = [1] * length
        temp = 1
        for i in range(1,length):
            result[i] = result[i-1] * a[i-1]
            
        for i in reversed(range(length)):
            result[i] = result[i] * temp
            temp *= a[i]

        return result