思路：
B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]，求A数组的连乘，但不包含A[i];
- 如果暴力，O(n²)
- 递归解决，分为两部分：
- 计算前部分： B[0] = 1
B[1] = A[1-1] * B[0] = A[0]
B[2] = A[2-1] * B[1] = A[0]* A[1]
...
B[i] = A[i-1] * B[i-1]... = A[0] A[1] ...A[i-1] - 计算后部分：i为最后一个索引下标
B[i] = 1* B[i] = A[0]* A[1] * ... * A[i-1]
B[i-1] = B[i-1] * A[i] = A[0] * A[1] ... A[i-2] * A[i]
...
B[0] = B[0] * A[1] * ... * A[i-1] = A[1] * ...* A[i-2] *A[i]
- 计算前部分： B[0] = 1
后半部分
for (int i = A.length - 1; i >= 0; i--) {
B[i] = tmp * B[i];
tmp *= A[i];
}
代码
/**
* B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]
* Created by liqiushi on 2018/3/24.
*/
public class Multiply {
public int[] multiply(int[] A) {
if (A == null) {
return null;
}
int[] B = new int[A.length];
if (B.length == 0) {
return B;
}
B[0] = 1;
//先计算了 B[i] = A[0]*A[1]*A[2]*...*A[i-1]
for (int i = 1; i < A.length; i++) {
B[i] = A[i - 1] * B[i - 1];
}
//后部分:
int tmp = 1;
/* for (int i = A.length - 2; i >= 0; i--) {
tmp *= A[i+1];
B[i] = tmp * B[i];
}*/
for (int i = A.length - 1; i >= 0; i--) {
B[i] = tmp * B[i];
tmp *= A[i];
}
return B;
}
}
