3

アルゴリズムのクラスで質問を受けましたが、解決できません。質問には、 Theres は を使用したソート アルゴリズムでO(nlogn)あり、検索は二分探索によって行われると記載されていO(log n)ます。2 つの集合が与えられており、2 つの集合が互いに素であるかどうかを判断するアルゴリズムを設計する必要がありますP。Q

4

2 に答える 2

5

O(N)解決策（2つのセットがソートされていると仮定）：

  1. 要素がどのセットに属しているかなどの情報を使用して、2 つのソートされたセットをマージします
  2. 結合リストをトラバースします。2 つのセットから 2 つの等しい要素が見つかった場合は、ばらばらではありません。

例えば

a= 1, 4, 6
b= 2, 4, 7

マージされた set=

要素: 1 2 4 4 6 7

セット番号 (a/b): 1 2 1 2 1 2

これで、2 つの 4 が連続しており、両方とも 2 つの異なるセットからのものであるため、ばらばらではないことがはっきりとわかります。

編集：

セットがばらばらであるか、単純なマージではないことを確認する必要がある場合は、それが得られます。セット内の両方の要素が等しいことがわかったらすぐに、バラバラではなく両方の終わりまで到達できる場合は、バラバラではないと言って戻ります。

コンテナに関する質問です。以下はそれです：

class Element{
int i;
int setInfo
}

配列を次のように宣言します。Element[] e=new Element[X];

私がはっきりしていることを願っています。

于 2013-10-20T03:31:27.450 に答える
2

これらの 2 つのセットの間に共通の要素がない場合にのみ、2 つのセットは互いに素になります。これらのセットの両方にそれぞれ n 個の要素があると仮定しています。このアルゴリズムは、nlog(n) 時間で共通要素をチェックします。共通の要素が見つからない場合は、両方のセットが素であることを意味します。

For each element in set "P" search whether that number exist in set "Q".
Time complexity - n*log(n) 
Log(n) to search in set Q and this search will be done "n" times.
于 2013-10-20T03:14:51.317 に答える