2

ソフトウェア開発者の面接の練習をしていて、アルゴリズムの質問に行き詰まりました。

Given two sets of unsorted integers with array of length m and other of 
length n and where m < n find an efficient algorithm to determine if 
the sets are disjoint. I've found solutions in O(nm) time, but haven't 
found any that are more efficient than this, such as in O(n log m) time.
4

4 に答える 4

9

O(1) ルックアップ/挿入を持つデータ構造を使用すると、最初のセットのすべての要素を簡単に挿入できます。

次に、2 番目のセットの foreach 要素は、存在する場合はばらばらではなく、そうでない場合はばらばらです

疑似コード

function isDisjoint(list1, list2)
    HashMap = new HashMap();
    foreach( x in list1)
        HashMap.put(x, true);

    foreach(y in list2)
        if(HashMap.hasKey(y))
             return false;
    return true;

これにより、O（n + m）ソリューションが得られます

于 2014-07-08T19:47:28.763 に答える
4

かなり明白なアプローチ - 長さの配列をソートm- O(m log m)。長さ の配列内のすべての要素について、nバイナリ検索を使用して、長さの配列内に存在するかどうかを確認しますm-O(log m)要素ごと = O(n log m)。であるためm<n、合計すると になりO(n log m)ます。

于 2014-07-08T19:46:47.603 に答える
3

Cheruvian が私を打ち負かしたように見えますが、ハッシュ テーブルを使用してO(n+m)平均的なケース
を取得でき ます: m. このステップはO(m)
* の各要素についてn、表にあるかどうかを確認します。そうであれば、false を返します。それ以外の場合は、次に進みます。これには がかかりますO(n)。
※表に無い場合はtrueを返します。

前に述べたように、ハッシュ テーブルは平均的なケースで一定のルックアップ時間を与えるため、これは機能します。多くの一意の要素mが同じハッシュを持つまれなイベントでは、少し時間がかかります。ただし、ほとんどの人は、想定される最悪のケースを気にする必要はありません。たとえば、クイック ソートは、O(n^2)上限があるにもかかわらず平均的なパフォーマンスが向上するため、マージ ソートよりもよく使用されます。

于 2014-07-08T20:03:27.630 に答える