[解決済み】数値の配列が与えられたとき、他のすべての数値の積の配列を返す（除算なし）

質問

面接でこの質問をされたのですが、他の人ならどう解くか知りたいです。私はJavaに最も慣れていますが、他の言語での解答も歓迎します。

数値の配列が与えられる。 nums の場合、数値の配列を返します。 products ここで products[i] は、すべての nums[j], j != i .

Input : [1, 2, 3, 4, 5]
Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)]
      = [120, 60, 40, 30, 24]

で行う必要があります。 O(N) を除算しないでください。

解き方は？

の説明 ポリジェンルブリカント というメソッドがあります。 配列の構成にコツがあります（4要素の場合）

{              1,         a[0],    a[0]*a[1],    a[0]*a[1]*a[2],  }
{ a[1]*a[2]*a[3],    a[2]*a[3],         a[3],                 1,  }

どちらも、左端と右端からそれぞれ開始することで、O(n)で実行できる。

そして、2つの配列を要素ごとに乗算すると、必要な結果が得られます。

私のコードは次のようなものです。

int a[N] // This is the input
int products_below[N];
p=1;
for(int i=0;i<N;++i) {
  products_below[i]=p;
  p*=a[i];
}

int products_above[N];
p=1;
for(int i=N-1;i>=0;--i) {
  products_above[i]=p;
  p*=a[i];
}

int products[N]; // This is the result
for(int i=0;i<N;++i) {
  products[i]=products_below[i]*products_above[i];
}

もし、空間的にもO(1)である必要があるのなら、このようにすることができます（IMHOではあまり明確ではありません）。

int a[N] // This is the input
int products[N];

// Get the products below the current index
p=1;
for(int i=0;i<N;++i) {
  products[i]=p;
  p*=a[i];
}

// Get the products above the curent index
p=1;
for(int i=N-1;i>=0;--i) {
  products[i]*=p;
  p*=a[i];
}