题解 | #构建乘积数组#

• 初始化数组B，用于保存最终乘积结果
• 先算左下角部分，此时 B[i] = A[0] 到 A[i-1] 的乘积
• temp 从右下角开始，保存每次循环内累乘的右上部分的结果
• 再算右上角部分，从 A[n-1] 遍历到 A[0] , 此时temp = A[i-1]到A[n]的乘积,B[i]=A[0]到A[n-1]乘积
• temp = A[i] 保存每次*循环内累乘的右上部分的结果

代码展示：

class Solution:
    def multiply(self, A):
        # write code here
        B = [0] * len(A)
        B[0] = 1
        # 先算左下角部分，此时B[i] = A[0]到A[i-1]的乘积
        for i in range(1, len(A)):
            B[i] = B[i-1] * A[i-1]
        tmp = 1
        for i in reversed(range(len(A))):
            # 两部分连接，从B[n-1]到B[0]连接上面的乘积结果
            B[i] *= tmp
            # # 右上角部分，从右下角开始向上计算
            tmp *= A[i]
        return B

复杂度分析：

算法思想二：动态规划

• 构建一维数组dp， dp[i] 表示A[0]到A[i]所对应的乘积
• 状态初始化，temp相当于保存左下角的乘积
• 从dp[2]开始动态规划更新
• 遇到A[i] = 1 则跳过计算，乘积结果也不变
• 实现 dp = dp * A[i];
• 拼接两部分乘积，保存下一部分的乘积

代码展示：

import java.util.ArrayList;
public class Solution {
    public int[] multiply(int[] A) {
        if(A == null || A.length == 0) {
            return new int[0];           
        }
        // dp[i] 表示A[0]到A[i]所对应的乘积
        int[] dp = new int[A.length];
        // 状态初始化
        dp[0] = A[1];
        dp[1] = A[0];
        // temp 相当于保存左下角的乘积
        int temp = dp[0] * dp[1];
        // 从dp[2]开始动态规划更新
        for(int i=2; i<A.length; i++){
            // 1 则跳过计算，乘积结果也不变
            if(A[i]!=1){
                // 实现 dp = dp * A[i];
                // 相当于在表格分区中，dp[j]对A[i]列累乘
                for(int j=0; j<i; j++){
                    dp[j] *= A[i];
                }
            }
            // 拼接乘积左下和右上部分的乘积
            dp[i] = temp;
            // temp 相当于左下角的乘积
            temp *= A[i];
        }
        return dp;
    }
}