算法思想一:表格分区,两次遍历

解题思路:

B[0]= 1 A[1] A[2] ... A[n-2] A[n-1]
B[1]= A[0] 1 A2
... A[n-2]
A[n-1]
B[2]= A[0]
A1
1 ... A[n-2]
A[n-1]
... ...
...
...
... ...
...
B[n-2]= A[0]
A[1]
A[2]
...
1 A[n-1]
B[n-1]=
A[0]
A[1]
A[2]
...
A[n-2]
1
左下角部分:从上到下计算并保存累乘结果
右上角部分:从下到上计算并保存累乘结果

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

代码展示:

Python版本
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):两个单层循环,N为数组长度
空间复杂度O(1):变量 tmp 使用常数大小额外空间


算法思想二:动态规划

解题思路:

运用动态规划思想,其实解题思路也相似,这样可以减少一次遍历
算法流程:
  • 构建一维数组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(1):变量 tmp 使用常数大小额外空间