6

高速なアルゴリズムを探しています:

サイズ n の int 配列があります。目標は、配列内のすべてのパターンを見つけることです。
x1, x2, x3 are different elements in the array, such that x1+x2 = x3

たとえば、サイズ 3 の int 配列があることを知っている場合、[1, 2, 3]可能性は 1 つしかありません: 1+2 = 3 (1+2 = 2+1 を考慮してください)

アルゴリズムを高速化するために、ペアとハッシュマップを実装することを考えています。（私が今手に入れた最速のものはまだですO(n^2))

この問題についてあなたの考えを共有してください、ありがとう

4

3 に答える 3

10

編集：以下の答えは、そのように合計される1つのトリプレットのみが必要なこの問題のバージョンに適用されます。それらすべてが必要な場合、少なくとも O(n^2) の可能な出力 (ex0du5 で指摘されているように) が存在する可能性があり、繰り返される要素の病理学的なケースでは O(n^3) でさえあるため、ハッシュ (値からその値を持つインデックスのリストへのマッピング) に基づく単純な O(n^2) アルゴリズムよりも優れています。

これは基本的に 3SUM 問題です。潜在的に無限に大きな要素がない場合、最もよく知られているアルゴリズムは約 ですが、ほとんどの計算モデルO(n^2)よりも高速にならないことを証明しただけです。O(n lg n)

整数要素が範囲内にある場合は、FFT[u, v]を使用して、これのわずかに異なるバージョンを実行できます。この問題をあの問題に変換し、そこで解決し、この変換に基づいて問題の答えを導き出すプロセスについて説明します。O(n + (v-u) lg (v-u))

私が FFT で解決する方法を知っている問題は、配列内で長さ 3 の算術シーケンスaをb見つけるcことc - b = b - aですa + c = 2b。

残念ながら、元の変換の最後のステップは、私が望むほど速くはありませんが、そこに到達したときにそれについて話します.

X整数を含む元の配列を呼び出しましょうx_1, ..., x_n。のようなインデックスi、を見つけたいと思います。jkx_i + x_j = x_k

  1. 時間内の最小値uと最大値vを見つけます。ありのままに。_ _XO(n)u'min(u, u*2)v'max(v, v*2)

  2. Z長さのバイナリ配列 (ビット文字列) を構築しv' - u' + 1ます。またはその doubleに が含まれてZ[i]いる場合は true になります。これは初期化です。の各要素を調べて、 の 2 つの対応する要素を設定するだけです。X[x_1*2, ..., x_n*2]u' + iO(n)XZ

    この配列を構築しているとき、見つかった重複のインデックスを補助リストに保存できますY。が完了したら、 for eachをZチェックします。存在する場合は、完了です。それ以外の場合、重複は無関係であり、忘れることができます。(わずかに複雑な唯一の状況は、が繰り返される場合です。その場合、解決策を得るには、その 3 つの異なるコピーが必要です。)2 * x_ix_iYY0

    ここで、問題の解、つまりは、 3 つの等間隔の解としてx_i + x_j = x_k表示されます。これは、いくつかの単純な代数操作によって が得られるためです。両端の要素は特別な二重エントリ ( から) であり、中央の要素は通常のエントリ ( から) であることに注意してください。Z2*x_j - x_k = x_k - 2*x_i2XX

  3. 次数の項の係数が であるZ多項式 の表現と考えてください。がの場合、は(1、2、3、4、5、6、および 10 があるため) です。は1 + x + x 2 + x 3 + x 4 + x 5 + x 9です。piZ[i]X[1, 2, 3, 5]Z1111110001p

    ここで、高校の代数から、2 つの多項式の積におけるx cの係数は、 x aに対する最初の多項式の係数の a + b = c にx bに対する2番目の係数を掛けた、すべての a、bの合計であることを思い出してください。したがって、q = p 2を考慮すると、 x 2j ( の a jの場合)の係数は、 のすべてのiの合計になります。しかし、は 2 進数であるため、これは で等間隔に配置されたトリプレットi、j、kの数とまったく同じです。（j、j、j）に注意してくださいZ[j] = 1Z[i] * Z[2*j - i]ZZは常にそのようなトリプレットであるため、値が 1 より大きいもののみを考慮します。

    次に、高速フーリエ変換を使用して、時間内にp 2を見つけることができます。ここで、は です。係数の別の配列を取得します。それを呼び出します。O(|Z| log |Z|)|Z|v' - u' + 1W

  4. x_kのそれぞれをループしますX。(必要な等間隔のものはすべて、Xではなくの要素を中心にしていることを思い出してください2*X。) この要素の 2 倍に対応するW、つまりW[2*(x_k - u')]が 1 である場合、それが自明でないプログレッションの中心ではないことがわかり、それをスキップできます。(前に議論したように、それは正の整数のみであるべきです。)

    それ以外の場合は、必要な進行の中心になる可能性があります (したがって、 と を見つける必要がありますi) j。しかし、残念なことに、それは私たちの望む形を持たない進行の中心である可能性もあります. したがって、確認する必要があります。の他の要素x_iをループし、,Xを含むトリプルがあるかどうかを確認します( を確認して)。もしそうなら、答えがあります。ヒットせずにすべて通過した場合、FFT は偽の答えしか見つけられず、 の別の要素をチェックする必要があります。2*x_ix_k2*x_jjZ[2*(x_k - x_j) - u']XW

    したがって、この最後のステップは O(n * 1 + (実際には解ではない W[2*(x_k - u')] > 1 の x_k の数))O(n^2)です。出力でこれらの誤った回答が生成されるのを回避する方法が必要Wです。適切なW係数が確実に答えを持っていることがわかっていれば、この最後のステップO(n)ですべてがうまくいくでしょう。

    これを行うために多少異なる多項式を使用することは可能だと思いますが、実際には機能していません。もう少し考えてみます……。

この回答に部分的に基づいています。

于 2012-04-24T18:51:17.623 に答える
1

他のメンバーをチェックできる n(n-1)/2 の異なる合計があるため、少なくとも O(n^2) である必要があります。合計されたペアは他のメンバーである可能性があるため、これらすべてを計算する必要があります (1 つの例から始めて、すべての要素を並べ替えて、すべてをチェックする必要があることを自分自身に納得させます)。または、具体的なものについてはフィボナッチを見てください。

したがって、それを計算してハッシュ テーブル内のメンバーを検索すると、償却された O(n^2) が得られます。または、最善の最悪のケースが必要な場合は、順序付けされたツリーを使用します。

于 2012-04-24T18:49:40.293 に答える
1

基本的に、値のペアのさまざまな合計をすべて見つける必要があるため、O(n 2 )よりもうまくいくとは思いません。ただし、リストを並べ替えて重複する値を減らすことで最適化できます。次に、値を同等以上のものとのみペアにし、合計がリストの最大値を超えたときに停止します。

于 2012-04-24T18:54:32.863 に答える