题目链接:https://leetcode.cn/problems/gou-jian-cheng-ji-shu-zu-lcof/
1. 题目介绍(66. 构建乘积数组)
给定一个数组
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. 题解
2.1 乘积矩阵 – O(n) ⭐
时间复杂度O(n),空间复杂度O(1)
【解题思路】:
除法: 如果没有不能使用除法的限制,我们则可以使用公式(A[0] * A[1] * ... * A[n-1] ) / A[i]
来求得 B[i];在使用除法时,只需要注意 A[i] 等于 0 的情况即可。
……
乘积数组:我们可以将B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]
分成两部分,一部分定义为C[i] = A[0]×A[1]×...×A[i-1]
= C[i-1] ×A[i-1];另一部分定义为D[i] = A[i+1]×…×A[n-1]
= D[i+1] × A[i+1]。那么我们就得到了 B[i]= C[i] ×D[i]
……
【实现策略】:
- 首选获取输入数组的长度
len1
,进行无效输入的判断;- 定义数组
B
, 用来存储返回结果;- 第一次循环,让
B[i]
累乘为C[i]
;- 第二次循环,让
B[i]
累乘为C[i] * D[i]
;- 最后返回结果。
class Solution {
// Solution1:B[i] = C[i] * D[i];
// C[i] = A[0] * ... * A[i-1];
// D[i] = A[i+1] * ... * A[n-1];
public int[] constructArr(int[] a) {
int len1 = a.length; // 获取数组A的长度
if (len1 <= 0) return new int[0]; // 无效输入判断
int[] b = new int[len1]; // 定义数组B,用来存储返回结果
b[0] = 1;
for (int i = 1; i < len1; i++) { // 累乘让 B[i] = C[i]
b[i] = b[i-1] * a[i-1];
}
int temp = 1;
for (int j = len1-2; j >= 0; j--) { // 累乘 让 C[i] * D[i]
temp *= a[j+1];
b[j] *= temp;
}
return b;
}
}