获取O(N)算法以查找具有奇怪约束的数字集合的乘积

Question

这是我参加最近一次采访的一个问题,我觉得很有意思.我们说int n = 10;

输入:一个数组 int a[10];

输出:一个数组 float b[10];

需求:

b[0]= a[1]*a[2]*...a[9];  //  product of all numbers in a, other than a[0]; 
b[1]= a[0]*a[2]*...a[9];  //  product of all numbers in a, other than a[1];
....
b[9]= a[0]*a[1]*...a[8];  //  product of all numbers in a, other than a[9];
....

问题:如何b在不使用除法运算符/的情况下填充数组？并用O(n)算法？

我尝试了很多方法,但仍然徒劳无功.有任何想法吗？

Answer 1

首先,计算所有左右产品:

left[i] = a[0]*a[1]*...*a[i]
right[i] = a[i]*a[i+1]*...*a[n-1]

请注意left[i] == left[i-1] * a[i],因此left可以在线性时间内计算数组.同样,right数组可以在线性时间内计算.

从left和right,b可以通过b[i] = left[i-1] * right[i+1]特殊情况i == 0和线性时间计算数组i == n.