描述

题目描述

给定一个数组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[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2];）

对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在。

示例

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

引言

遇到这种看似复杂、参数过多的问题，可以化繁为简，从简单例子开始理解题目

知识点：数组，遍历，动态规划
难度：⭐⭐⭐

题解

解题思路

本题有两个解法，一个是化为表格进行分区累乘，然后拼接累乘结果。

另一个是通过动态规划的思想解决。

方法一：表格分区，双向遍历

图解

算法流程：

• 初始化数组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] 保存每次*循环内累乘的右上部分的结果**

Java 版本代码如下：

import java.util.ArrayList;
public class Solution {
    public int[] multiply(int[] A) {
        if(A == null || A.length == 0) {
            return new int[0];            
        }
        int[] B = new int[A.length];
        // 初始化数组
        B[0] = 1;
        // 先算左下角部分，此时B[i] = A[0]到A[i-1]的乘积
        for(int i = 1; i < A.length; i++) {
            B[i] = B[i - 1] * A[i - 1];
        }
        // 从右下角开始，保存每次循环内累乘的右上部分的结果
        int temp = 1;
        // 再算右上角部分，此时temp = A[i-1]到A[n]的乘积,B[i]=A[0]到A[n-1]乘积
        for(int i = A.length - 1; i >= 0; i--) {
            // 两部分连接，从B[n-1]到B[0]连接上面的乘积结果
            B[i] *= temp;
            // 右下角开始，保存每次循环内累乘的右上部分的结果
            temp *= A[i];
        }
        return B;
    }
}

Python 版本代码如下：

# -*- coding:utf-8 -*-
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

复杂度分析：

时间复杂度 O(N)：两个单层 for 循环，N为数组长度
空间复杂度 O(N)：长度为N的数组保存乘积结果

总结：多画图，从简单例子入手，寻找规律

方法二：动态规划

运用动态规划思想，其实解题思路也相似，这样可以减少一次遍历

算法流程：

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

Java 版本代码如下：

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;
    }
}

复杂度分析：

时间复杂度 O(N)：for循环，N为数组长度
空间复杂度 O(N)：长度为N的数组保存每次状态

总结：灵活运用动态规划的状态转移过程