兩套物品。集合A中的每個元素集合B組比賽A的項中集B在O（nlogn）每個項目的唯一比賽時間

因此，要澄清一個問題：兩套物品。集合A中的每個元素集合B組比賽A的項中集B在O（nlogn）每個項目的唯一比賽時間

集A和B組每一個元素在集合A中有一個集合B 中的夥伴，您不能根據將它與同一集合的成員進行比較來排序集合，也就是說，B的每個b元素與集合B中的任何其他b都不可區分（對於A也是如此）。當Ai與Bi匹配時，您可以判斷是否Bi > Ai，Bi < Ai或Bi = Ai。設計一個O（nlogn）運行時間的算法。

二次時間顯而易見的答案是微不足道的，並沒有幫助 - 雖然這是我已經提出的最好的。 log（n）讓我認爲我應該使用遞歸或某種二叉樹，但我不確定如何在不能比較同一組中的元素的情況下創建二叉樹。另外，我不確定如何使用遞歸調用來獲得比僅運行嵌套的for循環更大的效果。任何提示將非常感謝。

來源

2012-10-11 slmyers

對它們排序並使用單個循環遍歷所有元素。如果你從一開始就有一組數據結構，那麼你可以取出迭代器並在其中循環。 – nhahtdh

所以你說A和B的相互之間沒有可比性，但是你可以比較每個A到每個B，並且需要找到對，例如'A == B'？ – verdesmarald

此問題基本上與gowaayacct所述的匹配螺母和螺栓問題相同。不過謝謝你的關注。 – slmyers

你還沒有說清楚，但你的問題看起來像Matching Nuts and Bolts問題可疑。

這個想法是選擇一個隨機的螺母a，找到匹配的螺栓b。使用螺母a對螺栓進行分區，然後使用螺栓b對螺母進行分區，然後遞歸，就像快速排序一樣。

（當然，我們談論的是平均情況是nlogn，而不是最壞的情況）。

來源

2012-10-11 05:49:18 goawayacct

非常感謝，這非常有幫助。我會盡量在將來更加清楚，如果我有名譽，我會爲您投票。 – slmyers

兩套物品。集合A中的每個元素集合B組比賽A的項中集B在O（nlogn）每個項目的唯一比賽時間

回答

相關問題