7

配列 [a1 To an] が与えられ、別の配列 [b1 To bn] where を作成する必要がありbi = a1*a2*…*an/aiます。定数スペースのみを使用でき、時間の複雑さは O(n) です。分割は許可されていません。

ソリューションのロジックは非常に単純です。製品から bi を削除して結果を取得します。しかし、この問題を解決するために処理したとき、私は自分自身が閉じ込められていることに気付きました。ここに私の疑問があります：

私の理解によると、ここでの一定のスペースは、配列の長さに関係なく、使用できる変数の数を固定する必要があることを意味します。問題を解決するために新しい配列を作成することを禁止します。新しい配列を作成すると、異なる配列を扱うときに変数の数が異なるためです。

このオンラインのほとんどのソリューションを検索しましたが、見つけることができるすべてのソリューションで新しいアレイが作成されました。それで、私はここで何か見逃しましたか？何かご意見は？どうもありがとうございました！

4

5 に答える 5

1

一定のスペース要件は、新しい配列の作成を禁止しません。これは、アルゴリズムが実行されるたびに同じ量のスペースを使用する必要があることを意味します。この質問では新しい配列を作成するように求められているので、一定の空間と線形時間でこれを行う関数を示します。

新しいアレイを作成することもできます。一定のサイズであることを確認してください。これを行う最も簡単な方法は、可能な限り最大のサイズにすることです。たとえば、C++ では次のように使用できます。

int* b  = new int[UINT_MAX];

配列で使用される最大のインデックスは UINT_MAX であるためです。これは、線形時間、一定空間、および必要に応じて新しい配列を構築するソリューションです。

int* prod(int *a, int len) {
    int* b  = new int[UINT_MAX];
    int tmp = 1;
    b[0] = 1;
    for (int i = 1; i < len; i += 1) b[i] = b[i - 1] * a[i - 1];
    for (int i = len - 1; i >= 0; i -= 1) {
        b[i] = b[i] * tmp;
        tmp *= a[i];
    } // for
    return b;
} // prod

関数のコントラクトは、新しい配列のサイズが入力配列と同じであることです (密かにそれが大きいことはわかっていますが)。もちろん、これはその場で計算するほど効率的ではありませんが、それは質問が求めていることではありません（少なくとも言葉遣いの方法）。

于 2013-10-14T22:27:20.987 に答える
0

問題を振り返ると、

  • 配列 [a1 .. an] が与えられます
  • 別の配列 [b1 .. bn] を構築します。ここで、bi = a1*a2*…*an/ai
  • 一定のスペースのみを使用でき、時間の複雑さは O(n) です
  • 分割は許可されていません

単純なアプローチは、除算を使用し、すべてを一度に計算することです。

#!/bin/env ruby #because I can
n = aray.size - 1
prod = 1
0.upto(n) { |x| prod *= aray[x] } 
0.upto(n) { |x| bray[x] = (aray[x]==0) ? 0 : prod/aray[x] }

私は bray[] を使用しましたが、簡単に結果を出力したり、array[] を置き換えたりすることができました。

しかし、問題文は割り算を許可していません。残念な。

代わりに、元の値を維持し、結果を bray[] に配置する必要があります。ここで、array[] を 2 回ループし、積を左から右に計算し、次に右から左に戻します。

#!/bin/env ruby #because I can
aray = [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 ]
bray = [ ]
n = aray.size-1
prod = 1
0.upto(n) { |ndx| bray[ndx] = prod; prod *= aray[ndx]; }
prod = 1
n.downto(0) { |ndx| bray[ndx] *= prod; prod *= aray[ndx]; }

結果を印刷し、

print "aray:\n";
aray.each_index { |ndx| print "[#{ndx}] #{aray[ndx]}\n" }
print "bray:\n";
bray.each_index { |ndx| print "[#{ndx}] #{bray[ndx]}\n" }
于 2013-10-15T02:21:22.353 に答える
0

これがプログラムのコア部分です。

与えられた

a[i] ここで、i の範囲は 0 から n-1 です

b[i] i の範囲は 0 から n-1 です。

デモ用に n = 4 と仮定します

コードはここから始まります

int count,sum=1;
for(count = 0; count < n; count++)
{
b[count] = sum;
sum *= a[count];
}
/*

カウント = 0 でループ

b[0] = 1;
sum = a[0]

count = 1 でループ

b[1] = a[0]
sum = a[0] a[1]

count = 2 でループ

b[2] = a[0] a[1]
sum = a[0] a[1] a[2]

count = 3 でループ

b[3] = a[0] a[1] a[2]
sum = a[0] a[1] a[2] a[3] -- This sum is not used at all

LOOPの最後に

b[0] = 1;
b[1] = a[0]
b[2] = a[0] a[1]
b[3] = a[0] a[1] a[2]

*/
sum = 1;
for(count = n-1; count >= 0; count--)
{
b[count] *= sum;
sum *= a[count];
}
/*

LOOP開始時

b[3] = a[0] a[1] a[2]
b[2] = a[0] a[1]
b[1] = a[0]
b[0] = 1;

count = 3 でループ

b[3] = a[0] a[1] a[2] -- multiplied with 1 will lead to the same answer
sum = a[3]

count = 2 でループ

b[2] = a[0] a[1] a[3]
sum = a[3] a[2]

count = 1 でループ

b[1] = a[0] a[2] a[3]
sum = a[3] a[2] a[1]

カウント = 0 でループ

b[0] = a[1] a[2] a[3] -- Multiplied with 1 will lead to the same answer
sum = a[3] a[2] a[1] a[0] -- This sum is not used at all.

LOOPの最後に

b[0] = a[1] a[2] a[3] 
b[1] = a[0] a[2] a[3]
b[2] = a[0] a[1] a[3]
b[3] = a[0] a[1] a[2]

*/

于 2016-08-31T19:50:04.880 に答える