面试题66. 构建乘积数组
2020-03-14 本文已影响0人
阿星啊阿星
题目描述
给定一个数组 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]。不能使用除法。
示例：
输入: [1,2,3,4,5]
输出: [120,60,40,30,24]
提示：
所有元素乘积之和不会溢出 32 位整数
a.length <= 100000
题目分析
U1S1这题大家都知道暴力法很快就能解出来，同时也知道暴力法存在着过多的重复运算；
接下来我们细细的揣测一下出题者的意愿（高中最爱的生物老师的名言），他要求的结果B[i] = A[0] * A[1] * ... * A[i-1] * A[i+1] * .... * A[n-1]，就是除了A[i]之外的数的累乘结果；
- 我们可以从A[i]出发，将B[i]分成两半，一半是A[0] * A[1] * ... * A[i-1]，另一半是 A[i+1] * .... * A[n-1]
- 对于B[i-1]，一半是A[0] * A[1] * ... * A[i-2]，另一半是 A[i] * .... * A[n-1]
- 到了找规律环节，B[i] 的左半边 = B[i-1]的左半边 * A[i-1]，B[i-1]的右半边 = B[i]右半边 * A[i]
-
结论：计算A[i]左半边累乘的时候可以利用A[i-1]左半边的累乘结果，计算A[i-1]右边累乘的时候可以利用A[i]右边累乘的结果，这样就可以大大减少重复运算。
image
fun constructArr(a: IntArray): IntArray {
val result = IntArray(a.size){1}
var leftMulti = 1
var rightMulti = 1
for(i in 0 until a.size){
result[i] *= leftMulti
leftMulti *= a[i]
}
for(i in a.size-1 downTo 0){
result[i] *= rightMulti
rightMulti *= a[i]
}
return result
}
我好了，完事了，你们呢
