构建乘积数组 python

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

思路一：
两层for循环，进行连乘，中间判断一下i != j 即可。时间复杂度O(n^2)

# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # # write code here
        #思路一：时间复杂度O(n^2)
        n = len(A)
        B = [1 for i in range(n)]
        for i in range(n):
            for j in range(n):
                if i != j:
                    B[i] *= A[j]
        return B

思路二：三角形问题，时间复杂度O(n)
[图片上传失败...(image-7281f5-1535524536475)]

第一步：计算下三角，也就是每行的【】之前的乘积

第一步：b[0] = 1;
第二步：b[1] = b[0] * a[0] = a[0]
第三步：b[2] = b[1] * a[1] = a[0] * a[1];
第四步：b[3] = b[2] * a[2] = a[0] * a[1] * a[2];
第五步：b[4] = b[3] * a[3] = a[0] * a[1] * a[2] * a[3];

第二步：计算上三角，也就是每行【】之后的乘积

第一步
temp *= a[4] = a[4];
b[3] = b[3] * temp = a[0] * a[1] * a[2] * a[4];
第二步
temp *= a[3] = a[4] * a[3];
b[2] = b[2] * temp = a[0] * a[1] * a[4] * a[3];
第三步
temp *= a[2] = a[4] * a[3] * a[2];
b[1] = b[1] * temp = a[0] * a[4] * a[3] * a[2];
第四步
temp *= a[1] = a[4] * a[3] * a[2] * a[1];
b[0] = b[0] * temp = a[4] * a[3] * a[2] * a[1];

# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # # write code here
        #思路二：时间复杂度O(n)
        n = len(A)
        B = [1 for i in range(n)]
        for i in range(1,n):
            B[i] = B[i-1] * A[i-1]
        tmp = 1
        for i in range(n-2,-1,-1):
            tmp *= A[i+1]
            B[i] *= tmp
        return B