题目：给定一个数组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
参考答案
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];
}
for (int i = A.length - 2, temp = 1; i >= 0; i--) {
temp *= A[i + 1];
B[i] *= temp;
}
return B;
}
}
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(1)。
网友评论