剑指offer 51. 构建乘积数组

51. 构建乘积数组

题目描述
给定一个数组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]。不能使用除法。

思路
思路一：
两重循环，在遍历数组A的时候，A[i]赋值为1，计算B[i]。时间复杂度为
思路二：
时间复杂度为
可以把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]分为两部分的乘积。效果相当于是个对角矩阵。

第一个for循环用来计算上图1范围的数，第二个for循环用来计算上图2范围的数。

代码实现
思路一：

 -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # write code here
        length = len(A)
        B = []
        if(length == 0):
            return B
        for i in range(length):
            temp = A[i]
            A[i] = 1
            Bi = 1
            for j in A:
                Bi *= j
            B.append(Bi)
            A[i] = temp
        return B

思路二：

# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # write code here
        length = len(A)
        if(length == 0):
            return []
        import copy   
        B = copy.copy(A)
        B[0] = 1
        # 计算下三角连乘
        for i in range(1,length):
            B[i] =  B[i-1] * A[i-1]
        # 计算下三角连乘
        temp = 1
        for j in range(length-2,-1,-1):
            temp *= A[j+1]
            B[j] *= temp
        return B