题目：给定一个数组 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]。不能使用除法。
练习地址
https://www.nowcoder.com/practice/94a4d381a68b47b7a8bed86f2975db46
https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof/
参考答案
public class Solution {
public int[] multiply(int[] A) {
if (A == null || A.length < 2) {
return A;
}
int[] B = new int[A.length];
B[0] = 1;
for (int i = 1; i < A.length; i++) {
B[i] = B[i - 1] * A[i - 1];
}
int temp = 1;
for (int i = A.length - 2; i >= 0; i--) {
temp *= A[i + 1];
B[i] *= temp;
}
return B;
}
}
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(1)。
