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 回答