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

Question

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

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

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

每组由 n 张卡组成，对于组 A 中的每张卡，组 B 中都有属于同一帐户的相应卡，我们将这两张卡称为匹配对。每张卡都是一个包含磁条的小塑料物体，磁 strip 有一些与银行中唯一帐户相对应的加密数字。需要找到所有匹配对。有一种读卡机，当两张卡插入机器时，一张来自 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.