描述
题目描述
给定一个数组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的数组保存每次状态
京公网安备 11010502036488号