7

[a_1 a_2 ... a_n](必ずしも異なる) 整数のリストを指定して、 のw,x,y,zような対ごとに異なるインデックスが存在するかどうかを判断しa_w + a_x = a_y + a_zます。

1 つの方法は、4 つのレベルのforループを使用し、それぞれがインデックスの 1 つを反復することです。合計が等しい場合は、すべてのインデックスがペアごとに異なるかどうかを確認します。そうであれば、 を返しtrueます。すべての可能性を使い果たした場合は、 を返しfalseます。これには実行時間がありO(n^4)ます。

もっとうまくやれるでしょうか？

4

3 に答える 3

4

のすべての可能な値を計算しa_w + a_x、それらをハッシュ テーブルに挿入します。(a_w + a_x, w) と (a_w + a_x, x) を 2 番目のハッシュ テーブルに挿入します。

最初のハッシュ テーブルに値を挿入する前に、値が既にテーブルにあるかどうかを確認します。その場合は、2 番目のテーブルを確認してください。(a_w + a_x, w) または (a_w + a_x, x) のいずれかが存在する場合は、何も挿入しないでください (要素が重複しています)。これらのペアのどちらも 2 番目のテーブルにない場合、肯定的な答えが得られます。

すべての (w, x) ペアを処理した後、肯定的な答えが得られない場合、これはそのようなペアごとに異なるインデックスがないことを意味します。

時間計算量は O(n 2 ) です。スペース要件も O(n 2 ) です。

O(n) 空間で同じことを行うことは可能ですが、O(n 2 * log(n)) 時間は、この回答からわずかに変更されたアルゴリズムを使用して実行できます:固定サブセット サイズの合計サブセット:

  1. リストを並べ替えます。
  2. a_w + a_xキーおよび値として含まれる要素の優先キューを使用w, xします。このキューにn-1要素を事前に入力します。ここで、x = 0 および w = 1 .. n-1 です。
  3. (sum, w, x)このキューから最小限の要素を繰り返し取り出し、要素をキューに入れ(a_w + a_x_plus_1, w, x+1)ます (ただし、x >= w の場合は要素を入れません)。キューから削除された 2 つの連続する要素の合計が同じになったら停止します。
  4. 重複を処理するために、合計が等しい 2 つの連続する要素の w、x を比較することができます。しかし、krjampani の前処理のアイデアを使用する方が簡単です。ソートされたリストに 2 組の重複が含まれているか、1 つの要素が 4 回重複している場合、成功です。それ以外の場合、重複する値は 1 つだけです。そのインスタンスを 1 つだけリストに残し、その 2 倍の値をインデックスの「特別な」ペア (2a, -1, -1) と共に優先キューに追加します。
于 2012-10-12T16:48:40.490 に答える
3

Evgeny の解決策は、元の配列を次のように前処理することで単純化することができます。

最初にハッシュ テーブルを使用して、元の配列内の各要素の頻度をカウントします。少なくとも 2 つの要素に重複がある場合 (それらの頻度は少なくとも 2 です)、または要素が少なくとも 4 つの頻度で発生する場合、答えはtrueです。それ以外の場合、要素aが頻度 2 または 3 で出現する場合、2 番目のハッシュ テーブルに追加し、元の配列内の単一のコピーで の2aすべてのコピーを置き換えます。a

次に、変更された配列で、インデックス の各ペアについてi、jを使用して 2 番目のハッシュ テーブルi < jに追加し、このハッシュ テーブルに重複するエントリが見つかった場合にa_i + a_j戻ります。true

于 2012-10-12T17:55:26.333 に答える
0

8.5 GB のメモリがある場合 (unsigned int の場合はより多く、合計またはインデックスが int の範囲全体に及ばない場合はより少なくなります)、3 つの配列を作成します。まず、可能な合計ごとに 1 ビットを使用します。結果のビットマップです。Second は、可能な合計ごとに 32 ビットを使用します。インデックス j を記録します。3 番目は、可能な合計ごとに 1 ビットを使用します。これは、その合計が現在の反復で検出されたかどうかを記録するビットフィールドです。i--各反復でそれをゼロにします。i=0...n と j=i+1...n を繰り返します。各合計について、最初のビットフィールドに設定されているかどうかを確認します (以前に発生した場合)。そうである場合、2 番目の配列に記録されたインデックスが i または j のいずれかと一致するかどうかを確認します (古い j が新しい i または新しい j と一致する場合)。そうでない場合は、2 番目の配列のビットが設定されていることを確認します (現在の反復で設定されているため、古い i が新しい i と一致する場合)。そうでない場合は、一致しています。(古い i は古い j や新しい j と一致することはなく、新しい i は新しい j と一致することはありません。) 終了します。それ以外の場合は、3 つの配列すべての合計を記録して続行します。

40 ドル相当のメモリを使用しますが (私は現在が大好きです :)、これはおそらくハッシュ マップとボクシングを使用するよりもはるかに高速です。n が大きいとメモリ使用量が少なくなる場合もあります。欠点の 1 つは、データが L2 キャッシュに存在することはほとんどないことです。ただし、少なくとも TLB ミスがメイン メモリにも行かないように、JVM がヒュージ ページを使用するように設定してみてください。処理は o(n^2)、メモリは o(1) です。

于 2012-10-12T19:35:19.210 に答える