41

2 つのセットが与えられた場合に、それらの交差を線形時間で計算するアルゴリズムはありますか?

2 つのループを実行forして要素のすべてのペアをチェックし、両方のセットで見つかった要素を記録できます。ただし、実行時間は O(n 2 ) になります。これを O(n) 時間で行うにはどうすればよいですか?

4

6 に答える 6

48

それはあなたのセットの実装に依存します。

ハッシュ セット (O(1) ルックアップ) がある場合、他のすべての投稿者が示したアプローチは正しいです。最初のセットのすべての要素を反復処理します。2 番目のセットにある場合は、結果に追加します。これは O(n) 時間で実行されます。

ツリー セット (O(lg n) ルックアップ) がある場合、このアプローチは機能しますが、O(n lg n) 時間で実行されます。もっと上手にできます。O(n) ソリューションがあります。2 つのセットの要素を昇順でトラバースできるある種の反復子があると仮定します。もしそうなら、問題は「2 つのリストをソートされた順序で与えて、それらの交点を見つけること」です。これは、2 つの範囲をマージするために使用するアルゴリズムの修正版を使用して行うことができます。アイデアは、2 つの反復子を追跡することです。各ステップで、範囲の最初の要素を比較します。それらが等しい場合は、要素を交差点に追加し、両方の反復子を前方に進めます。1 番目が 2 番目よりも小さい場合は、最初のイテレータを進めます。最初の要素の方が大きい場合は、2 番目の反復子を進めます。

于 2011-01-09T22:18:41.683 に答える
12

誰もハッシュテーブルについて言及していないのだろうか。
setの実装に関係なく（ここでの「set」は単純な配列を意味します）、次のことができます。

  1. 最初のセットの内容をハッシュテーブルに入れて
  2. 2番目のセットを繰り返し、ハッシュテーブルに現在の要素が含まれているかどうかを確認します。

O(n)

于 2011-01-09T22:55:47.067 に答える
4 
intersection(a, b):
  result = new empty set
  for x in b:
    if a contains x:
      add x to result

  return result

containsテストが一定時間 (実装としてハッシュ テーブルを使用するセットなど) である場合、このアルゴリズムはO(n).

于 2011-01-09T22:14:38.173 に答える
2

2 つの配列を結合し、この結合された配列内の各要素の出現回数を数え、これらを新しい配列に入れます。次に、このカウント配列をチェックして、2 を含むエントリを探します。これらの要素は、2 つのセットの交差部分にあります。

于 2014-02-25T17:58:38.030 に答える
0

2 つのリストのいずれかが順序付けされている場合、順序付けられていないリストから開始できます。

FUNCTION: INTERSECTION ( LIST A, LIST B )
{
   CREATE C AS EMPTY LIST

   FOR EVERY: NUMBER n IN A
   {
        IF BINARY-SEARCH(n) IN B
        {
            ADD n TO C
        }
   }

   RETURN C
}

Time Complexity = O(n O(BINARY-SEARCH)) = O(n log n)

リスト B がhashedの場合、BIG-THETA(C n + T(hash))

ここで、BIG-THETA は漸近平均であり、Cおよびconstant はT(hash)ハッシュ関数に必要な時間です。

于 2012-06-15T13:13:29.993 に答える
0

セット 1 のすべての要素について: その要素がセット 2 にあるかどうかを確認します。O(1) ルックアップ時間を償却したセットを実装できます。

于 2011-01-09T22:13:47.037 に答える