剑指51-构建乘积数组

Posted on | In |

题目描述

给定一个数组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]的计算公式一次计算B中每个元素。该方法牵涉到大量的重复的乘运算，效率较低。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def multiply(self, A):
        # write code here
        if len(A) == 0:
            return None
        if len(A) == 1:
            return [0]
        B = []
        for i in range(len(A)):
            val = 1
            for j in range(len(A)):
                if j != i:
                    val *= A[j]
            B.append(val)
        return B

令C[i] = A[0]*A[1]*...*A[i-1]，D[i] = A[i+1]*...*A[n-1]，则B[i] = C[i]*D[i]。且有C[i+1]=C[i]*A[i]和D[i]=A[i+1]*D[i+1]。可以大大简化乘运算数量。如下版本的代码还避免了新数组的构建，空间效率也比较高。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def multiply(self, A):
        # write code here
        if len(A) == 0:
            return None
        if len(A) == 1:
            return [0]
        B = [1]
        for i in range(1, len(A)):
            B.append(B[i-1]*A[i-1])
        temp = 1
        for j in range(len(A)-2, -1, -1):
            temp *= A[j+1]
            B[j] *= temp
        return B