arrays - 匹配具有相同值但不同顺序的两个数组的有效算法

Question

我们知道两个数组A的B大小n具有相同的一组不同的整数值，但可能以不同的方式排序，因此两个数组之间存在一对一的匹配。我们不知道数组中存储的实际值，也无法访问数组的值，因此无法使用 sorted 等函数。然而，我们可能会询问任何一对A[i]and的问题B[j]，并得到是否A[i] = B[j],A[i] > B[j]或的答案A[i] < B[j]。

A将每个元素与其对应的元素匹配的有效算法是B什么？我想到的第一件事是一种简单的蛮力方法，首先通过反复询问和for to之间的关系问题A[1]与其对应的匹配项匹配，直到找到匹配项。然后对for to执行相同的操作以找到其余s 的匹配项。最坏情况下的运行时间是. 但这似乎不是最有效的方法，因为我们只使用了是否 的信息，而没有使用是否或的更详细信息。直觉上应该有一种方法可以利用和之间的相对顺序BA[1]B[j]j = 1nA[i]i = 2nA[i]n + (n - 1) + ... + 1 = O(n^2)A[i] = B[j]A[i] > B[j]A[i] < B[j]A[i]B[j]在更短的O(n^2)时间内设计一个算法。

任何帮助将不胜感激！

标签： arraysalgorithmmatching

Answer 1

由于您无法比较同一数组中的元素，因此您无法单独对它们进行排序，但您可以进行一种相互快速排序，仍然在预期的 O(N log N) 时间内：

1. 选择 A 的一个元素作为 A 轴
2. 根据 B 的元素与 A 轴的比较方式对 B 的元素进行分区。其中之一将比较相等。那就是B轴
3. 根据它们如何比较 B 轴对 A 的元素进行分区。如果存在 1-1 匹配，则分区将与 B 的分区大小相同。
4. 在较低的 A 和 B 分区以及较高的 A 和 B 分区上递归。