algorithm - 两套元素。集合 A 的每个元素在集合 B 中唯一匹配。在 O(nlogn) 时间内将集合 A 的每个项目与集合 B 中的项目匹配

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，找到匹配的 bolt b。使用螺母 a 划分 bolt ，使用 bolt b 划分螺母，然后递归，就像快速排序一样。

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