JZ66 构建乘积数组

发表于 分类于 本文字数： 578 阅读时长 ≈ 2 分钟

JZ66 构建乘积数组

描述

给定一个数组$A[0,1,…,n-1]$ ,请构建一个数组 $B[0,1,…,n-1]$ ,其中 B 的元素$B[i]=A[0]\times A[1]\times …\times A[i-1]\times A[i+1]\times …\times A[n-1]$。 即$B[i]$为除$A[i]$以外的全部元素的的乘积。程序中不能使用除法。

（注意：规定 $B[0] = A[1] * A[2] * … * A[n-1]，B[n-1] = A[0] * A[1] * … * A[n-2]$）

对于 A 长度为 1 的情况，B 无意义，故而无法构建，用例中不包括这种情况。

数据范围：$1≤n≤10 $ ，数组中元素满足 $∣val∣≤10 $

示例1

1
2
输入：[1,2,3,4,5]
返回值：[120,60,40,30,24]

示例2

1
2
输入：[100,50]
返回值：[50,100]

题解

我用$N^2$的方法做了一个，然后看题解发现有这样一种方法，有些绕，但是我大概理解了。

如下图所示：

JZ66_diagram

矩阵中由对角线1将其分成了上三角和下三角。我们先看下三角，如果我们累乘的时候，B[1]是在B[0]的基础上乘了一个新增的A[0]，B[2]是在B[1]的基础上乘了新增的一个A[1]，那我们可以在遍历数组的过程中不断将数组B的前一个数与数组A的前一个数相乘就得到了下三角中数组B的当前数。同理在上三角中用一个变量存储从右到左的累乘，每次只多乘一个数字，这样两次遍历就可以解决了。

解释

这张图按行来看，每行就是B所对应的元素乘积，不管是上三角还是下三角的遍历过程中，每次都借助前一个B和A的记录来更新当前B，有一些动态规划的思想。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#
# @param A int整型一维数组
# @return int整型一维数组
#
class Solution:
    def multiply(self, A: List[int]) -> List[int]:
        # 初始化数组B
        B = [1 for i in range(len(A))]
        # 先乘左边，从左到右
        for i in range(1, len(A)):
            # 每多一位由数组B左边的元素多乘一个前面A的元素
            B[i] = B[i - 1] * A[i - 1]
        temp = 1
        # 再乘右边，从右到左
        for i in reversed(range(len(A))):
            # temp为右边的累乘
            B[i] *= temp
            temp *= A[i]
        return B