实现将盖子与正确大小的罐子匹配的算法 [英] Implementing an algorithm that matches lids to jars of the correct size

问题描述

问题:我们得到了一个罐子列表和一个盖子(相同大小)列表.每个罐子至少要有一个匹配的盖子，反之亦然.在给出的列表中，盖子和罐子都是随机打乱的.我想找到一种有效的算法来返回配对的盖子和罐子.

The problem: We're given a list of jars and a list of lids (same size). For each jar, there is at least one matching lid and vice versa. In the lists that are given, both the lids and jars are scrambled randomly. I want to find an efficient algorithm to return pairs of matching lids and jars.

我的策略:使用高效的算法(log(n)，n =罐数=盖数)对两组数据进行排序.然后，我们可以将它们两两匹配成对，然后将它们添加到将作为结果输出的列表中.

My strategy: sort both sets, using an efficient algorithm (log(n), n = number of jars = numbers of lids). Then we can just match them two-by-two into a pair, which we add to a list that will be the resulting output.

仅限制:罐子不能与罐子和盖子 不能与罐子进行比较.可以对罐子和盖子进行比较(jar.compareTo(lid)或lid.compareTo(jar)).

Only restriction: jars cannot be compared to jars and lids cannot be compared to lids. A comparison between jars and lids is possible to make (jar.compareTo(lid) or lid.compareTo(jar)).

想法 :(快速排序)选择一个枢轴式广口瓶并将盖子分成三组: 1)盖对于所选参考盖来说太小，2)与该盖匹配的盖(至少有一个这样的盖)，3)对于所选枢轴而言太大的盖.不建议为这些子组创建新列表(就像在QuickSort中一样)，因此我们通过连续的交换对盒盖进行分区(集合具有交换方法).

Idea: (QuickSort) Choose a pivotal jar and divide the lids into three groups: 1) The lids that are too small for the chosen reference lid, 2) the lid that matches this lid (there is at least one such lid), 3) the lids that are too large for the chosen pivot. Making new list for these subgroups is not recommended (just like in QuickSort), so we partition the lids via successive swaps (Collections have a swap method).

我相信我们可以选择一个随机的枢轴盖以类似的方式分隔罐子.现在，我认为递归可能是对我们形成的子列表进行排序的一种可能性.

I believe that we can just select a random pivotal lid to partition the jars in a similar way. Now, I think that recursion could be a possibility to sort the sublist that we have formed.

该策略听起来很简单，但事实证明该实现并不那么琐碎.我什至不知道从哪里开始.我是否需要为子列表中的递归调用使用单独的方法?我如何不使用f.ex来完成所有这些工作. copyOfRange(即复制给定列表的子集)?是否有一个相关的图形理论问题，已经有一个现有的实现?

As simple as this strategy may sound, the implementation turned out not to be so trivial. I actually don't even know where to start. Do I need to seperate methods for the recursive calls in the sublists? How can I do all of this without using f.ex. copyOfRange (i.e. copying a subset of the given lists)? Is there a related graph theoretical problem, that already has an existing implementation?

提前谢谢！

推荐答案

本网站在解释如何实现QuickSort方面做得很好. 它甚至包含一个实现.

This site does a great job explaining how to implement QuickSort. It even contains an implementation.

网站上的一些要点是:

您的分区方法将仅对您指定的数组部分进行分区，因此您无需使用copyOfRange进行复制.开始时，您将对整个数组进行分区，然后使用递归对枢轴之前的部分和之后的部分进行分区.

Your partition method will only partition the section of the array you specify, so you don't need to make a copy using copyOfRange. When it starts you partition the whole array, then partition the part before and the part after the pivot using recursion.

您可以使用随机枢轴.由于实际上并没有什么不同，因此您也可以放弃随机部分，而只使用数组的第一个元素.

You can use a random pivot. Since it doesn't really make a difference, you could also forgo the random part and simply use the first element of the array.

这篇关于实现将盖子与正确大小的罐子匹配的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！