一、题目
给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即：B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
二、示例
2.1> 示例:
【输入】 [1,2,3,4,5]
【输出】 [120,60,40,30,24]
提示：
- 所有元素乘积之和不会溢出
32位整数 - a.length <=
100000
三、解题思路
根据这道题的描述，我们其实很容易就想到，现遍历数组中所有的元素，然后针对每个元素执行乘法操作，得到最终的结果之后，如果需要获得B[i]的值，只需要将总的结果除以A[i]即可。但是，本道题已经指明了不能使用除法，那么上面我们最容易想出来的解决方案就不能使用了。
那么还有什么解决办法吗？我们以A[1,2,3,4,5]为例，如果要组成B数组，需要如下方式计算（其中“口”表示略过不计算）:
B[0] =
口* 2 * 3 * 4 * 5
B[1] = 1 *口* 3 * 4 * 5
B[2] = 1 * 2 *口* 4 * 5
B[3] = 1 * 2 * 3 *口* 5
B[4] = 1 * 2 * 3 * 4 *口
那么根据上面从B[0]~B[4]的计算公式可以看出来，整个“计算矩阵”是被口分割为两个三角，我们姑且将其称之为“左下角三角”和“右上角三角”。那么针对每个B[i]，我们可以得出如下计算公式，即：B[i] = 左下三角区域[i] ✖️ 右上三角区域[i] 。那么我们执行如下方式执行遍历计算：
【正序遍历】从
B[0]开始到B[n-1]，计算的结果是“左下三角形”的值；
【逆序遍历】从B[n-1]开始到B[0]，在计算“右上三角形”值的同时，再乘以左下三角区域[i]的值，那么就是B[i]最终的结果了。
以上就是这道题的解题思路了，下面我们还是举一个例子，这样更方便和深入的让大家理解这道题的解题过程，我们以A数组为{1,2,3,4,5}为例，来看一下计算B数组的过程。请见下图所示：
四、代码实现
class Solution {
public int[] constructArr(int[] a) {
int len = a.length;
if (len == 0) return a;
int[] result = new int[len];
result[0] = 1;
// 计算左下三角的乘积
for (int i = 1; i < len; i++)
result[i] = result[i-1] * a[i-1];
// 计算右上三角的乘积
for (int i = len - 2, temp = 1 ; i >= 0; i--) {
temp *= a[i+1];
result[i] *= temp;
}
return result;
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
网友评论