平均情况 nlogn 螺母和螺栓匹配

Question

我必须制定一个算法来匹配两个数组中的项目，我们不允许先对任何一个数组进行排序，我们只能通过与数组 1 中的项目和数组 2 中的项目进行比较来匹配（比较是<,=,>).输出是两个列表，它们具有相同的顺序。我可以想办法用n(n+1)/2次来解决它。目标是 nlog(n)。我一直在用头撞墙想办法，但我做不到。谁能给我提示？

所以要解释输入是两个数组ex。 A = [1,3,6,2,5,4] B =[4,2,3,5,1,6] 并且输出是具有相同顺序的两个数组。您不能首先单独对数组进行排序或比较同一数组中的项目。您只能比较列表中的项目，例如 A_1

Answer 1

类似于快速排序：

使用随机的 A 元素将 B 划分为较小的 B、相等的 B 和较大的 B。使用其相等的 B 元素对 A 进行分区。递归地将较小的 A 与较小的 B 以及较大的 A 与较大的 B 进行匹配。

就像快速排序一样，预期时间是 O(n log n)，最坏情况是 O(n²)。