試験で次の質問が出されましたが、それは不可能のようです。足りないものはありますか？
等しいかどうかのみを比較できる n 個のオブジェクトの配列が与えられ、配列内の値の範囲について何も知らない場合、配列内の重複の存在を検出するための分割統治ソリューションを提供します。これは O(nlogn) ソリューションでなければなりません。
質問の性質上、解決策はデータ構造や基数ソートとは関係がない可能性が高いと想定できますが、これはインプレースで実行できますか?
もしそうなら、どのように？
質問する
2910 次
6 に答える
1
ハッシュセットを使用するのはどうですか。各アイテムをセットに追加します。次に、サイズを確認します。ただし、これは分割統治ではありません。
等しいかどうかを比較した結果、比較されている 2 つのオブジェクトのどちらが「大きい」かがわかりますか?
オブジェクトのセットの全体的な順序付けを作成できる場合は、インプレース分割および conq ソート アルゴリズムの 1 つを使用して、重複を検出するロジックを追加できると考えています。(<= チェックを < および == チェックに変える)
于 2012-04-12T16:51:36.657 に答える
0
NlogN時間でそれを行う唯一の方法は、「チート」することです。
.NET および Java では、Equals() メソッドのみを公開する .NET の IEquatable のようなインターフェイスの実装も、基本レベルのオブジェクトです。.NET と Java のオブジェクトにはハッシュ関数があります (.NET では GetHashCode()、Java では hashCode())。そのため、インターフェースによって制限されているメソッドに関係なく、数値を生成するハッシュ関数に常にアクセスできます。
これにより、各オブジェクトをハッシュし、ハッシュを比較して相対的な大きさを確認できます。これにより、配列をハッシュでソートし、線形時間でスキャンして重複を検出できます。これをその場で行うことも、ハッシュ値をキーにした赤黒木、ハッシュテーブル、または辞書に各項目を挿入することで、元の配列をそのまま残すこともできます (これらはすべて、logN 以上のアクセス時間と logN 以上の挿入があります)。回）。
コメントで述べたように、これらのアプローチはいずれも複数のスレッドに並列化できるため、「分割統治」要件が可能になります。並べ替えは並列 MergeSort で実行できますが、環境内でアクセスできるオブジェクトに応じて、スレッドセーフな「同時」コレクションを使用できます。これにより、配列をコレクションに挿入されたサブ配列に分割できます。複数のスレッド。ソートされたリストのスキャンは、各スレッドに指定されたサブ配列を 1 つの要素でオーバーラップさせて並列化することもできます。これにより、重複するペアの 1 つの項目が 1 つのサブ配列にあり、もう 1 つの項目がセレンディピティによって次のサブ配列にあることが防止されます。
于 2012-04-12T18:02:36.447 に答える
0
たぶん、分析を検討する別の方法がありますか？
同意、O(N^2) の最悪のケース。しかし、最良のケースは O(1) です。
のみが存在し、値の範囲が不明であるという事実だけを見るequalと、N^2 を取得する方法は 1 つだけで、それはすべての値が異なる、または等しくない場合であると言えますか?
同様に、1 回のテストで重複を見つけることを保証する唯一の方法は、すべての値が等しい場合です。
同一のペアを見つける前にすべてのオブジェクトを比較することが不可能な場合が多数あります。N/2 ペア、N/3 トリプル、N/4 クォード、N/sqrt(N) セットの sqrt(N) 重複などがある場合、ペア、つまり重複を見つける前にいくつを比較する必要がありますか?
これは、「同一の靴下が 2 つ以上セットになっている状態で、同じ靴下の数が不明な靴下抽選から 1 組の靴下を見つける」のようなものだと思います。靴下抽選の所有者は、同じ靴下を何足か購入することで抽選を補充し、穴が開いた靴下を捨てます。靴下がどれだけ早くすり減るか、または所有者がどれだけ早く靴下を購入するかはわかりません。
平均して、N^2 よりもはるかに優れたパフォーマンスが期待できるのではないでしょうか?
于 2012-04-12T18:47:30.027 に答える