集合Mが与えられた場合、両方ともMに属する数のペア（a、b）があるかどうかを調べ、a + b = xです。ここで、xは以前に指定されたパラメーターです。この問題は、分割統治をO（n * log n）で使用して解決する必要があります。おそらく、問題を2つの半分のサイズのサブ問題に分割してから、結果をO（n）で再結合する必要があります。
与えられた問題の擬似コードまたはそれを解決するためのヒントが欲しいのですが。
1220 次
2 に答える
3
これが要件に適合するかどうかはわかりませんが、次のようになります。
- セットをマージソートします（これは分割統治法を使用します）。
- セットの最初と最後の要素から始めて、それらの合計をxと比較します。合計が等しい場合は、完了です。合計が大きい場合は、最後から2番目の要素にステップダウンし、合計が小さい場合は、2番目の要素にステップアップします。
- xに合計される要素が見つかるか、要素がなくなるまで、並べ替えられたセットの端から中央に向かって、手順2を繰り返します。
分割統治ソートはO（n lg n）であり、ソートされたセットのステップスルーはO（n）であるため、全体の複雑さはO（n lg n）です。
Ed：Mではなくxに合計します。
于 2011-05-30T13:00:02.810 に答える
2
Mを（D＆Iを使用してO（n log n）で）ソートすると、正しい合計のペアがあるかどうかを線形時間でチェックできます。（ヒント：2つのポインター）。
それがD＆Iソリューションとしてカウントされないと思われる場合は、チェックステップを並べ替えの結合ステップに折りたたんで、一致するものが見つかったら早期に終了することができます。
追加：結合中にチェックを行うと、O（n）の代わりにO（n log n）の加算と比較のステップを実行することになりますが、もちろん、定数を除いて漸近ランタイムを悪化させることはありません要素。
于 2011-05-30T13:02:38.060 に答える