algorithm - 找到两个相同大小数组的元素之间的唯一映射

Question

我最近在面试中被问到这个问题:

有两个大小为 'n' 的数组。一排有螺母，另一排有 bolt 。每个螺母正好适合一个 bolt ，反之亦然。当您将螺母与 bolt 进行比较时，您会得到以下 3 个结果之一:紧、松、配合。

如何高效地找到唯一映射？

无法对任何一组进行排序。你永远不知道 b1 是否小于 b2 或
n1 小于 n2。其中 n1,n2 是螺母，b1,b2 是 bolt 。您唯一能做的就是将螺母与 bolt 进行比较，然后得出结果:紧、配合、松。

Answer 1

类似快速排序的算法可以完成这项工作:

1. 随机选择一个螺母 n 并将其用作枢轴将 bolt 组 B 分成三组:紧(B1)，宽松 (B2)，合身。
2. 将配合 bolt 标记为b。现在，您使用此 bolt 作为枢轴将螺母集 N\n 分成两组:紧密 (N1) 或松散 (N2)。
3. 现在你有三对:N1 和 B1，n 和 b，N2 和 B2。它们都具有相同的大小。您可以递归地对 (N1,B2) 和 (N2,B1) 进行相同的划分，您可以获得最终答案。

很明显复杂度是O(N log N)，和quicksort一样。