就職面接でこの質問をされたのですが、他の人はどのように解決するのか知りたいです。私は 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)これを除算を使わずに行う必要があります。
ベストアンサー1
説明ポリジェネ潤滑剤方法は次のとおりです。
コツは配列を構築することです (要素が 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];
int 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) である必要がある場合は、次のようにします (私の意見では、これはあまり明確ではありません)。
int a[N] // This is the input
int products[N];
// Get the products below the current index
int p = 1;
for (int i = 0; i < N; ++i) {
products[i] = p;
p *= a[i];
}
// Get the products above the current index
p = 1;
for (int i = N - 1; i >= 0; --i) {
products[i] *= p;
p *= a[i];
}