问题：我们得到了一个罐子列表和一个盖子（相同大小）列表。每个罐子至少有一个匹配的盖子，反之亦然。在给出的列表中，盖子和罐子都是随机打乱的。我想找到一种有效的算法来返回匹配的盖子和罐子对。
我的策略：使用高效算法（log（n），n =罐子的数量=盖子的数量）对两个集合进行排序。然后，我们可以将它们两两匹配成对，然后将它们添加到将作为结果输出的列表中。
唯一的限制：罐子不能与罐子相比，盖子不能与罐子相比。可以在罐子和盖子之间进行比较（jar.compareTo（lid）或lid.compareTo（jar））。
想法：（QuickSort）选择一个枢轴式广口瓶并将盖子分成三组：
1）盖对于所选参考盖而言太小，2）与该盖相匹配的盖（至少有一个这样的盖），3）对于所选枢轴而言太大的盖。不建议为这些子组创建新列表（就像在QuickSort中一样），因此我们通过连续的交换对盒盖进行分区（集合具有交换方法）。
我相信我们可以选择一个随机的枢轴盖以类似的方式分隔罐子。现在，我认为递归可能是对我们形成的子列表进行排序的一种可能性。
尽管听起来很简单，但事实证明实现起来并不那么琐碎。我什至不知道从哪里开始。我是否需要为子列表中的递归调用单独使用方法？我如何不使用f.ex来完成所有这些工作。 copyOfRange（即复制给定列表的子集）？是否有一个相关的图形理论问题，已经有一个现有的实现？
先感谢您！
最佳答案
This site在解释如何实现QuickSort方面做得很好。
它甚至包含一个实现。
该网站的一些要点是：
您的分区方法只会对您指定的数组部分进行分区，因此您无需使用copyOfRange进行复制。开始时，您将对整个数组进行分区，然后使用递归对枢轴之前和之后的部分进行分区。
您可以使用随机枢轴。由于实际上并没有什么不同，因此您也可以放弃随机部分，而只使用数组的第一个元素。