問題:それぞれサイズ n の 2 つの並べ替えられた配列 A[] と B[] が与えられた場合、空でない交差があるかどうかを確認します (交差自体は必要ありません。決定のみが必要です)。
解決策: A[] の各要素に対して B[] でバイナリ ソートを行うと、O(n lg n) の解が得られます。各配列を最初から最後まで繰り返す (Mergesort の Merge と非常によく似た処理を行う) と、O(n) の解が得られます。
（複雑さの点で）より良い解決策があるかどうか疑問に思っていました。私はそうではないと確信していますが、「ちょっと、もっと良い解決策を教えてくれたら、o(n lg n) でベクトルをソートできますが、それは不可能です」を探していました-kind-of-argument
問題をもう一度読んでください - ."Given two sorted arrays ..."
最初に提案された並べ替えは必要ありません。これによりO(n)、マージ並べ替えのようなプロセスを実行するソリューションが得られます。
マージソートのようなプロセスよりもはるかに優れた方法はありません。交差が見つかった場合は早期に停止できることを覚えておいてください。
ソートされていない場合:
ハッシュ マップ ベースのソリューションは、技術的には次のようになりますO(n)。A のすべての要素をハッシュ マップに挿入します ( O(n))。B ( ) 内の各要素のルックアップを実行しますO(n)。
並べ替えソリューションの場合、必要なのは決定だけなので、A を並べ替えて B をループし、BO(log n)の各要素に対して A でルックアップを実行し、項目が見つかったら停止するだけです。よりもうまくいくことはありませんがO(n log n)、一致が早期に見つかった場合、作業を半分まで削減できます。