algorithm - 获取 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 数组可以在线性时间内计算。类似地，正确的数组可以在线性时间内计算。

从left和right，数组b可以在线性时间内通过b[i] = left[i -1] * right[i+1] 具有 i == 0 和 i == n 的特殊情况。