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可以在线性时间内计算数组。同样，right可以在线性时间内计算数组。

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

Answer 2

根据 Egor Skriptunoff 的想法，我写了这段代码： 更容易理解：

        float l[n];
        float r[n];
        left[0] = 1;
        right[n-1] = 1;
        for (int i=1; i<n; i++)
        {
            l[i] = l[i-1]*a[i-1];
        }
        for (int i=n-2; i>=0; i--)
        {
            r[i] = r[i+1]*a[i+1];
        }
        for (int i=0; i<n; i++)
        {
            b[i] = l[i]*r[i];
        }