arrays - 如何在两个数组中查找倒序对？

Question

这是一个 interview question .有两个数组 A1 和 A2。找出 A2 中与 A1 中顺序相反的数字对。例如，A1 = [2 6 5 8 1 3]，A2 = [1 2 3 4 5 6]。答案:(1, 2), (1, 5), (1, 6), (5, 6), (3, 5), (3, 6)。

O(N^2) 算法很简单。有没有更好的算法？你怎么看？

Answer 1

如果你有像 A1 = 1111122222 和 A2 = 2222211111 这样的模式，那么你将输出 (N/2)⁴ 对.因此，在最坏的情况下，你不能比 O(N⁴) 做得更好。

下面是一个复杂度为 O(N⁴) 的解决方案，它处理重复项和一些仅出现在两个列表之一中的数字。请注意，虽然在最坏情况下它是 O(N⁴)，但 O(N²) 的平均情况更有可能，类似于快速的复杂性-排序。

index = {} # dictionary of lists defaulting to []
for i in 0..len(A2):
  index[A2[i]].append(i)
for i1 in 0..len(A1):
  for j1 in i+1..len(A1):
    for i2 in index[A1[i1]]:
      for j2 in index[A1[j1]]:
        if i2 != j2 and i1 < j1 != i2 < j2:
          print A1[i1], A1[j1]

如果我们稍微放宽输出格式以允许输出 (1, 2) * 7 来表示 7 次反转，那么我们可以做得更好。首先压缩列表，给出 [(2, 1), (6, 2), (5, 3), (8, 4), (1, 5), (3, 6)]例如。使用稳定排序对数组进行排序:首先使用每个元组中的第一项，然后使用元组中的第二项对列表的另一个副本进行排序。然后使用一种适应的合并排序，如提到的 here ，但不是计算我们生产我们输出反转。这是一个 O(NlogN) 的解决方案。