题目描述
给定一个数组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]。不能使用除法。（注意：规定B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2];）
题解一
如果能用除法的话，那么可以将A数组中所有元素相乘，使用这个乘积除以A[i]，即可得到B[i]。但由于题目限制不使用除法，另一个直观的解法是将A数组按照i的位置分为两部分，然后连乘这两部分中的所有元素即可。这里给出两种实现方法。
时间复杂度为，空间复杂度为
。
下面是参考代码：
public int[] multiply(int[] A) {
int[] B = new int[A.length];
for (int i = 0; i < A.length; i++) {
B[i] = 1;
for (int j = 0; j < i; j++)
B[i] *= A[j];
for (int j = i+1; j < A.length; j++)
B[i] *= A[j];
}
return B;
}
public int[] constructArr(int[] a) {
int[] res = new int[a.length];
for (int i = 0; i < a.length; i++) {
int temp = 1;
for (int j = 0; j < a.length; j++) {
if (j == i) continue;
temp *= a[j];
}
res[i] = temp;
}
return res;
}
题解二
这里是剑指中的思路，非常巧妙。
数组B可以用一个矩阵来创建，此时B[i]的值就是矩阵中每行的乘积。定义C数组保存下三角每行乘积的值，定义D数组保存上三角每行乘积的值。因此C[i] = C[i-1] * A[i-1], D[i] = D[i+1] * A[i+1]，最后再将C和D数组中的对应元素相乘得到B数组。
把数组B看成一个矩阵来创建
时间复杂度为，空间复杂度为
。
下面是参考代码：
class Solution {
public int[] constructArr(int[] A) {
int n = A.length;
if (n == 0)
return new int[0];
int[] B = new int[n], C = new int[n], D = new int[n];
C[0] = 1; D[n-1] = 1;
// 计算下三角
for (int i = 1; i < n; i++)
C[i] = C[i-1] * A[i-1];
// 计算上三角
for (int i = n-2; i >= 0 ; i--)
D[i] = D[i+1] * A[i+1];
// 计算B数组
for (int i = 0; i < n; i++)
B[i] = C[i] * D[i];
return B;
}
}
