两套物品。集合A的每个元素在集合B中唯一匹配。匹配集合A的每个项目到集合B中的项目的时间为O(nlogn)

Question

因此，为了澄清这个问题：

集合A和集合B集合A中的每个元素在集合B中都有一个伙伴你不能通过将其与同一集合的成员进行比较来对任何一个集合进行排序，即B中的每个b元素与集合B中的任何其他b元素都是不可区分的(A也是如此)。当Ai与Bi匹配时，你可以分辨出Bi > Ai、Bi < Ai或Bi = Ai。设计了一个运行时间为O(nlogn)的算法。

二次方时间的明显答案是微不足道的，也没有什么帮助--尽管这是我想出的最好的答案。log(n)让我认为我应该使用递归或某种类型的二叉树，但我不确定如果不能比较同一集合中的元素，如何创建二叉树。此外，我不确定如何使用递归调用来获得比仅运行嵌套for循环更好的效果。任何建议都将不胜感激。

Answer 1

您没有很清楚地说明这一点，但是您的问题看起来很像Matching Nuts and Bolts问题。

这里的想法是随机挑选一个螺母a，找到匹配的螺栓b。使用螺母a划分螺栓，使用bolt b划分螺母，然后像快速排序一样递归。

(当然，我们讨论的是nlogn的平均情况，而不是最坏的情况)。