题目描述
给定一个数组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长度为1的情况，B无意义，故而无法构建，因此该情况不会存在。
输入
[1,2,3,4,5]
输出
[120,60,40,30,24]
思路以及解答
由于这道题不可以使用除法，如果使用暴力做法的话，需要每一个数值，都计算其他所有数的乘积，那这样的算法时间复杂度是O(n2),空间复杂度为O(n)，显然是不符合要求的。
public int[] multiply(int[] A) {
if(A!=null) {
int []nums = new int[A.length];
for (int i = 0; i < A.length; i++) {
int result = 1;
for (int j = 0; j < A.length; j++) {
// 跳过自身
if (j == i)
continue;
// 其他的都乘起来
result *= A[j];
}
nums[i]= result;
}
return nums;
}
return null;
}
再想想更优的做法，可以分解开看。最后的结果中，每一个数，都是等于它左边的所有数，乘以它右边的所有数。
那么我们可以申请一个数组，假设为B[]，第一次遍历的数组A[]的时候，把每一个数A[i]左边的所有数的乘积，乘起来，放在B[i]的位置。此时，每一个数左边的乘积已经有了，如何计算右边的乘积呢？
可以同样申请一个数组C[]存起来，但是没有必要，因为我们从右边往左边遍历的时候，只需要用一个临时变量，把右边的乘积存着，和左边的乘积相乘，赋值到原来的数组A[]，就可以了。
代码如下：
public int[] multiply(int[] A) {
if (A == null || A.length < 2)
return null;
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;
}
上面的做法相当于申请了大小为n的临时空间，空间复杂度为O(n)，遍历了数组两遍，时间复杂度为O(2n)，也就是O(n)。
