題目：給定一個(gè)數(shù)組 A[0,1,...,n-1]，請(qǐng)構(gòu)建一個(gè)數(shù)組 B[0,1,...,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×...×A[i-1]×A[i+1]×...×A[n-1]。不能使用除法。
練習(xí)地址
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;
}
}
復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(n)。
- 空間復(fù)雜度：O(1)。
