1

私はRobertSedgewickの著書AlgorithmsからAlgorithmsを読んでいて、しばらくの間、運動の問題に悩まされてきました。ここに質問があります：

それぞれ3つの名前のリストが与えられNた場合、3つのリストすべてに共通の名前があるかどうかを判断するためのアルゴリズムを見つけます。アルゴリズムはO（Nlog N）の複雑さを持っている必要があります。使用できるのは並べ替えアルゴリズムのみであり、使用できるデータ構造はスタックとキューのみです。

HashMapを使用してこの問題を解決できると思いましたが、質問によって解決が制限されています。それでも、NlogNの複雑さはありません。

4

2 に答える 2

3

各リストを並べ替える場合、リストAの名を選択して、その要素が<の場合、リストBの名と比較することで、3つのリストすべてにO（n）時間で1つの名前があるかどうかを簡単に確認できます。リストAの場合は、リストb要素をポップし、リストB> =リストAになるまで繰り返します。一致が見つかった場合は、Cでプロセスを繰り返します。Cでも一致が見つかった場合はtrueを返し、そうでない場合は、 。

ここで、すべてのリストをnlogn時間で並べ替える必要があります。これは、スタックとキューだけを使用して少しクリエイティブにする必要がありますが、お気に入りの並べ替えアルゴリズムで実行できます。おそらくマージソートをお勧めします

以下の疑似コードは、繰り返し処理しているリストを変更しているため、少し混乱しています。

擬似コード：listA、b、およびcがソートされたキューであり、最小の名前がキューの先頭にあると想定します。

eltB = listB.pop()
eltC = listC.pop()
for eltA in listA:
    while(eltB<=eltA):
        if eltB==eltA:                
            while(eltC<=eltB):
                if eltB==eltC:
                    return true
                if eltC<eltB:
                    eltC=listC.pop();
        eltB=listB.pop()
于 2012-09-28T17:02:50.413 に答える
0

手順:

  1. O(N lgN)並べ替えアルゴリズムを使用して 3 つのリストを並べ替えます。
  2. 各リストから 1 つの項目をポップします。
  3. ポップしようとしたリストのいずれかが空の場合、完了です。つまり、共通の要素は存在しません。
  4. それ以外の場合は、3 つの要素を比較します。
  5. 要素が等しい場合、完了です。共通の要素が見つかりました。
  6. それ以外の場合は、3 つの要素の最大値を維持し (一定時間) 、2 つの要素が破棄された同じリストから補充します。
  7. 手順 3 に進みます。

ステップ 1 が必要O(N lgN)で、残りのステップが必要O(N)なので、全体の複雑さはO(N lgN)です。

于 2012-09-29T01:48:29.577 に答える