题目描述：
给定一个数组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[i]公式中没有a[i]项，也就是说如果可以使用除法，就可以用公式b[i]=a[0]a[1].....*a[n-1]/a[i]来计算b[i]，但是题目要求不能使用，因此我们只能另想办法。
现在要求不能使用除法，只能用其他方法。一个直观的解法是用连乘n-1个数字得到b[i]。显然这个方法需要o(n*n)的时间复杂度。
好在还有更高效的算法。可以把b[i]=a[0]a[1].....a[i-1]a[i 1].....a[n-1]。看成a[0]a[1].....a[i-1]和a[i 1].....a[n-2]*a[n-1]两部分的乘积。
即通过a[i]项将b[i]分为两部分的乘积。效果如下图所示：
不妨设定c[i]=a[0]a[1]...a[i-1]，d[i]=a[i 1]...a[n-2]a[n-1]。c[i]可以用自上而下的顺序计算出来，即c[i]=c[i-1]a[i-1]。类似的，d[i]可以用自下而上的顺序计算出来，即d[i]=d[i 1]a[i 1]。
如果还是不明白，没有关系，直接看下代码，细细体会下就懂了。
第一个for循环用来计算上图1范围的数，第二个for循环用来计算上图2范围的数。
代码实现(c )
class solution {
public:
vector multiply(const vector& a) {
int length = a.size();
vector b(length);
if(length <= 0){
return b;
}
b[0] = 1;
for(int i = 1; i < length; i ){
b[i] = b[i - 1] * a[i - 1];
}
int temp = 1;
for(int i = length - 2; i >= 0; i--){
temp *= a[i 1];
b[i] *= temp;
}
return b;
}
};
代码实现(python)
python可以利用reduce方法快速求解。
# -*- coding:utf-8 -*-
class solution:
def multiply(self, a):
# write code here
b = []
if len(a) == 0:
return b
else:
for i in range(len(a)):
tmp = a[i]
a[i] = 1
b.append(reduce(lambda x,y:x*y, a))
a[i] = tmp
return b