Github仓库地址:https://github.com/Damaer/CodeSolution 刷题笔记地址:https://damaer.github.io/CodeSolution/ 仓库介绍:刷题仓库:CodeSolution
给定一个数组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)
。
【作者简介】:
秦怀,公众号【秦怀杂货店】作者,技术之路不在一时,山高水长,纵使缓慢,驰而不息。个人写作方向:Java源码解析,JDBC,Mybatis,Spring,redis,分布式,剑指Offer,LeetCode等,认真写好每一篇文章,不喜欢标题党,不喜欢花里胡哨,大多写系列文章,不能保证我写的都完全正确,但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处,还望指正。
平日时间宝贵,只能使用晚上以及周末时间学习写作 - END -