2つのソート済みリストの交差のための最も速いアルゴリズムは何ですか？

Question

AとBの2つの並べ替えられたリストがあるとします。

AとBのエントリ数は異なる場合があります。 （彼らは非常に小さくても巨大であってもよく、お互いに似ていてもかなり異なっていてもよい）。

この機能のための最も速いアルゴリズムとして知られているものは何ですか？

私にアイデアやリファレンスを与えることはできますか？

Answer 1

はAはm要素を有し、Bがm ≥ nとn要素を有していると仮定する。空の交差点を検証するために、我々は基本的にソートマージを実行する必要があるため情報は、理論的に、私たちができる最善のは、

(m + n)! 
lg -------- = n lg (m/n) + O(n) 
    m! n! 

の比較です。この境界の定数の範囲内では、Bを反復し、Bの最新の要素がソートされた順序を維持するために挿入される位置を示すAに「カーソル」を保持することによって達成できます。我々はx_1 + x_2 + ... + x_n = m + nはmのいくつかの整数分割である

lg x_1 + lg x_2 + ... + lg x_n, 

程度であるトータルコストのために、カーソルを進めるためexponential searchを使用します。この合計は、lgの凹みによってO(n lg (m/n))である。

Answer 2

が、これは最速のオプションであれば、私は知りませんが、ここでnとmはあなたのリストのサイズですO(n+m)で実行する1だ整数

for(int i = A.size() - 1; i > -1; --i){ 
    Integer currentInteger = A.get(i); 
    if(!B.remove(currentInteger)) 
     A.remove(currentInteger); 
} 

Answer 3

と2つのリストAとBがあると仮定します。そのうちの一つは、次のように空になるまで、両方のリストの上に

• ループ：1、リスト上の一つ
• アドバンス。
• 他のリストの現在の値以上の値が見つかるまで、他のリストに進む。
• 等しい場合、要素は交差点に属し、別のリストに追加することができます
• 他の要素より大きい場合は、この値以上の値が見つかるまで他の要素に進みます
• 言ったように、リストの1まで、これを繰り返しては空です。この機能のための最速のアルゴリズムであることが知られているどのよう

Answer 4

？

利用二つのリストががにソートされている場合に最良であるmerge sort技術。組み合わせソートリストを取得するには、O(n+m)が必要です。

2つのリストをトラバースせずに並べ替えることはできません。あなたが達成できる最高のものはO(n+m)です。行うにはどのように

：、両方のリストの先頭から始めて比較し、ピックアップ低い値を、インクリメンタルドナーリスト内の次に移動し、一方または両方のリストが空になるまで繰り返し。 1つのリストが空でない場合は、結果のリストに追加するだけです。