5

したがって、質問を明確にするために：

セット A とセット B セット A のすべての要素にはセット B のパートナーがあり、同じセットのメンバーとの比較に基づいてどちらのセットも並べ替えることができません。つまり、B の各 b 要素はセット B の他の b と区別できません ( A)についても同様です。Ai が Bi と一致するとBi > Ai、Bi < AiかかがわかりますBi = Ai。実行時間が O(nlogn) のアルゴリズムを設計します。

二次時間での明白な答えは些細で役に立ちませんが、これは私が今まで思いついた中で最高のものです。log(n) を見ると、再帰または何らかのバイナリ ツリーを使用する必要があると思われますが、同じセットの要素を比較できずにバイナリ ツリーを作成する方法がわかりません。また、ネストされた for ループを実行するよりも効果的な再帰呼び出しを使用する方法もわかりません。どんなヒントでも大歓迎です。

4

1 に答える 1

9

あなたはそれをあまり明確に述べていませんが、あなたの質問は不審にナットとボルトのマッチングの問題のように見えます。

ランダムなナットaを選び、一致するボルトbを見つけるというアイデアがあります。ナットaを使用してボルトを分割し、ボルトbを使用してナットを分割してから、クイックソートのように繰り返します。

（もちろん、最悪のケースではなく、平均的なケースがnlognであることについて話しています）。

于 2012-10-11T05:49:18.093 に答える