我们知道大小为n的两个数组A,B具有相同的不同整数值集合，但可能排序方式不同，因此两个数组之间存在一对一匹配。我们不知道数组中存储的实际值，并且无法访问数组的值，因此不能使用sorted等函数。然而，我们可以问任何一对A[i]和B[j]，得到A[i] = B[j],A[i] > B[j]或A[i] < B[j]的答案。
将每个元素A匹配到B中的相应元素的有效算法是什么?我首先想到的是一个简单的蛮力方法，首先通过反复询问j = 1和n之间A[1]和B[j]之间的关系问题，将A[1]与B中的对应项进行匹配，直到我们找到匹配。然后对i = 2到n的A[i]执行相同的操作，以找到A[i]s的其余部分的匹配。最坏情况下的运行时间是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)的时间内设计一个算法。
任何帮助都将非常感激!
由于不能比较同一数组中的元素，因此不能单独对它们进行排序，但可以进行某种相互快速排序，仍然在预期的O(N log N)时间内:
- 选择A中的一个元素作为A轴
- 根据它们与a枢轴的比较划分B的元素。其中一个比较相等。这是b轴
- 根据它们与b枢轴的比较方式划分A的元素。如果存在1-1匹配，分区将与B的分区大小相同。
- 在下面的A和B分区以及上面的A和B分区上递归。
下面是我对这个问题的尝试:
from collections import defaultdict
a = [1,2,4,5,8]
b = [8,5,4,1,2]
d = defaultdict(list) #(element,index) map
for i,v in enumerate(a):
d[v]=[i]
for j,x in enumerate(b):
d[x].append(j)
print(d)
非常简单。我为一个数组创建了一个元素来索引映射，并使用它来匹配第二个数组的键。
时间复杂度:O(n)空间复杂度:O(n)
试图找到一个O(1)的空间复杂度解决方案，这可以直观地使用分而治之的方法来完成，利用我们可以请求每个元素的指定查询。将很快更新。
OP问题不太清楚。首先，他说这些元素是整数，但他又说他只能用2乘2比较它们，这表明他不能对它们进行哈希。下面是一个解决方案，如果不可能哈希:
我将对两个数组进行排序，保持元素的位置沿着元素。然后，您可以检查排序值是否相等，并根据位置找到匹配的值。它是O(n log(n))
val1 = ["1", "5", "3", "6"]
val2 = ["3", "6", "1", "5"]
// Key = ... means to compare i and j, compare val1[i] with val2[j]
val1s = sorted(range(len(val1)), key = lambda i: val1[i])
// The result is
val1s
[0, 2, 1, 3]
// which is effectively the order in which val1 must be read to have it sorted...
val2s = sorted(range(len(val2)), key = lambda i: val2[i])
perm = [None]*len(val1)
for i in range(len(val1)):
perm[val1s[i]] = val2s[i]
perm
[2, 3, 0, 1]
注意:代码与任何具有可比性的东西(例如:字符串)逐字执行。
编辑:我在回答评论"你不能对数组排序，因为你不知道数组元素"。这在某种意义上是错误的。而不是排序数组(我不允许改变它)，我返回一个列表，它给出了正确的顺序来读取要排序的数组。完全有可能在不访问元素的情况下得到它。查看python代码
下面是Matt算法的Python实现。
AB创建并隐藏A和B，只提供比较A[i]和B[j]，检查索引列表I和J是否完全匹配。quickmatch为求解算法
显示计算的I,J以及它们是否完美匹配的演示输出:
[16, 0, 19, 7, 10, 15, 12, 14, 5, 4, 11, 18, 1, 9, 2, 6, 13, 8, 3, 17]
[1, 3, 13, 12, 0, 18, 9, 4, 14, 17, 11, 6, 5, 7, 15, 2, 8, 10, 16, 19]
True
代码:
from random import shuffle
class AB:
def __init__(self, n):
A = list(range(n))
B = list(range(n))
shuffle(A)
shuffle(B)
def cmp(i, j):
a = A[i]
b = B[j]
return -1 if a < b else 1 if a > b else 0
def check(I, J):
if not (sorted(I) == sorted(J) == list(range(n))):
return False
return all(A[i] == B[j] for i, j in zip(I, J))
self.cmp = cmp
self.check = check
def quickmatch(I, J):
if not I:
return I, J
ipivot = I[0]
jpivot = next(j for j in J if ab.cmp(ipivot, j) == 0)
small_I = [i for i in I if ab.cmp(i, jpivot) < 0]
small_J = [j for j in J if ab.cmp(ipivot, j) > 0]
small_I, small_J = quickmatch(small_I, small_J)
large_I = [i for i in I if ab.cmp(i, jpivot) > 0]
large_J = [j for j in J if ab.cmp(ipivot, j) < 0]
large_I, large_J = quickmatch(large_I, large_J)
return (small_I + [ipivot] + large_I,
small_J + [jpivot] + large_J)
# Create a test case
n = 20
ab = AB(n)
# Solve
I = list(range(n))
J = list(range(n))
I, J = quickmatch(I, J)
# Check
print(I)
print(J)
print(ab.check(I, J))