2

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

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

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

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

4

2 回答 2

4

您可以使用卡片形式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.
于 2013-10-30T08:01:09.380 回答
1

我认为在这个问题上滥用分区是明智的。

来自维基百科：

在快速排序中，有一个称为分区的子过程，它可以在线性时间内将列表（从左到右的索引）分为两部分，小于某个元素的部分和大于或等于该元素的部分。

考虑以下算法。

  1. 从 A 组中选择任何一张牌。我们称它为1。
  2. 使用读卡器对集合 B 进行分区，以便将集合 B 分成 3 个子集，即等于 card a 1的子集、小于 card a 1的子集和大于 card a 1的子集。
  3. 永远只有一张卡等于卡 a 1。我们称这张牌为 b 1。
  4. 将卡片 b 1及其配对卡片 a 1 插入“二叉搜索树”类型的事物中
  5. 从集合 A 中选择另一张牌，称之为2。
  6. 使用读卡器将它与 b1 进行比较，如果它小于 b 1，则在步骤 (2) 的子集上运行一个分区，其中 b k < a 1。如果它大于 b 1，则在步骤（2）的子集上运行一个分区，其中 b k > a 2。这是 O(n / 2)，因为我们在较小的集合上运行分区。
  7. 从集合 B 中取出等于 a 2的卡片，将其称为 b 2，并将其插入到步骤 (4) 中的二叉树中（通过与集合 A 中先前匹配的项目进行比较来插入）。
  8. 重复 a 3、 a 4等，继续将集合 B 分解为越来越小的集合，并使用二叉​​搜索树找到“正确”的分区集合来搜索k in。

最终你会得到像 O(n) + 2* O(n / 2) + 2* O(n / 4) + 2* O(n / 8) 等这样的时间复杂度。使用每个正确配对的二叉搜索树，我相信时间复杂度将是 O(n log n)。在最坏的情况下，它显然是 O(n^2)，就像快速排序一样。

最终你会得到一个排序的二叉树，其中每个节点都包含一对匹配的卡片。

于 2013-10-30T08:10:58.477 回答