2セットのアイテム。</p> <p>セットAとセットB すべての要素：の各要素は、質問を明確にするために、そう

Question

O（nlogn）時間にセットB.試合でユニークなマッチに集合B内の項目に集合Aの各項目を設定しますセットAにはパートナーBがあります 同じセットのメンバーと比較してセットをソートすることはできません。つまり、Bの各bエレメントはセットBの他のbと区別できません（Aと同様）。 AiがBiとマッチすると、Bi > Ai、Bi < Ai、またはBi = Aiのいずれかになります。 実行時間がO（nlogn）のアルゴリズムを設計する。

二次的な時間を使った明白な答えは簡単ではありませんが、私がまだ思いついたことは最高です。 log（n）は再帰やある種のバイナリツリーを使うべきだと思うが、同じセットの要素を比較することができずにバイナリツリーを作成する方法がわからない。また、ループのネストを実行するだけでなく、より大きな効果を再帰的に呼び出す方法もわかりません。どんなヒントも大歓迎です。

Answer 1

あなたはそれを明確に述べていませんが、質問にはMatching Nuts and Boltsのような疑問があります。

ランダムなナットaを選ぶというアイデアがある場合は、一致するボルトbを探します。ナットaを使用してボルトを分割し、ボルトbを使用してナットを仕切り、quicksortのように再帰します。

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