在 O(nlogn) 内找到两个集合中的匹配对

Question

有一个大小为 n 的集合 A 和集合 B，集合 A 中的每张卡在集合 B 中都有对应的卡。

描述一种更有效的算法，平均情况复杂度为 O(nlogn) 测试来查找匹配对。证明您的算法满足所需的复杂性。

我想我可以使用快速排序对每个集合进行排序，即 nlogn + nlogn，然后我就会知道每个集合中的相应位置是匹配对。这是正确的吗？这是问题的全部

每组由 n 张卡组成，组 A 中的每张卡在组 B 中都有一张属于同一帐户的对应卡，我们将这两张卡称为匹配对。每张卡都是一个小塑料物体，其中包含一个磁条，磁条上有一些加密数字，与银行中的一个唯一帐户相对应。需要找到所有匹配对。有一种读卡机，当两张卡插入机器时，一张来自A组，一张来自B组，机器的三个指示灯之一亮；如果配对匹配，则为绿色；如果 A 上的帐号大于 B 上的帐号，则为红色；如果 B 上的帐号大于 A 上的帐号，则为黄色。但是，读卡器无法比较属于同一组的两张卡。

Answer 1

可以用卡片形式A集合作为枢轴来快速选择集合B。这样就可以实现快速排序。因此，从 A 组中选择一张卡，并将 B 组分成更小和更大的卡片。如果您在 B 中找到了匹配的卡，您可以使用这张卡来划分 A 组。如果您没有找到匹配的卡，请重复。如果找到，则以与快速排序相同的方式将算法应用于较小和较大的组。重复直到找到所有匹配的卡片。复杂度与快速排序相同，因此最坏情况下为 O(n^2)，平均为 O(NlogN)。

Erlang 中的示例实现：

-module(abcards).

-export([find_pairs/2]).

find_pairs([], _) -> [];
find_pairs(_, []) -> [];
find_pairs([A|As], Bs) ->
  case partitionB(A, Bs, [], [], not_found) of
    {_, _, not_found} -> find_pairs(As, Bs);
    {BLess, BMore, B} ->
      {ALess, AMore} = partitionA(B, As, [], []),
      [{A, B} | find_pairs(ALess, BLess) ++ find_pairs(AMore, BMore) ]
  end.

card_reader(A, B) when A > B -> red;
card_reader(A, B) when A == B -> green;
card_reader(A, B) when A < B -> yellow.

partitionB(_, [], BLess, BMore, Found) -> {BLess, BMore, Found};
partitionB(A, [B|Bs], BLess, BMore, Found) ->
  case card_reader(A, B) of
    red -> partitionB(A, Bs, [B|BLess], BMore, Found);
    green -> partitionB(A, Bs, BLess, BMore, B);
    yellow -> partitionB(A, Bs, BLess, [B|BMore], Found)
  end.

partitionA(_, [], ALess, AMore) -> {ALess, AMore};
partitionA(B, [A|As], ALess, AMore) ->
  case card_reader(A, B) of
    red -> partitionA(B, As, ALess, [A|AMore]);
    yellow -> partitionA(B, As, [A|ALess], AMore)
  end.