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配列bを線形時間で計算できます。b[i] = left[i-1] * right[i+1]i == 0i == n