剑指Offer系列（java版，详细解析）66.构建乘积数组
题目描述
剑指 Offer 66. 构建乘积数组
难度中等108
给定一个数组 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]。不能使用除法。
示例:
输入: [1,2,3,4,5]
输出: [120,60,40,30,24]
提示：
- 所有元素乘积之和不会溢出 32 位整数
a.length <= 100000
测试用例
- 功能测试（输入数组包含整数、负数、一个0、多个0）
- 边界值测试（输入数组的长度为0）
题目考点
- 考察应聘者的发散思维能力。
- 考察应聘者对数组的理解和编程能力。
解题思路
- 从左往右累乘(但是保证B[i] = A[0] *…* A[i-1])
- 从右往左累乘(但是保证B[i] = B[i] * A[n-1] * … * A[i + 1])
参考解题
class Solution {
public int[] constructArr(int[] a) {
if(a.length == 0) return new int[0];
int[] b = new int[a.length];
b[0] = 1;
int tmp = 1;
for(int i = 1; i < a.length; i++) {
b[i] = b[i - 1] * a[i - 1];
}
for(int i = a.length - 2; i >= 0; i--) {
tmp *= a[i + 1];
b[i] *= tmp;
}
return b;
}
}
补充
通过保存或者利用中间过程是降低时间复杂度的可行方法。