高效地find可变数量的string集合的交集

我有一个可变数量的ArrayList的，我需要find的交集。 string数量的现实上限大概是35左右，但可能更多。 我不想要任何代码，只是想法什么是有效的。 我有一个实现，即将开始编码，但想听听其他一些想法。

目前，只是想着我的解决scheme，看起来我应该有一个渐近的Θ（n ² ）运行时间。

感谢您的帮助！

tshred

编辑：澄清，我真的只是想知道有没有更快的方式来做到这一点。 比Θ（n ² ）更快。

Answer 1

Set.retainAll()是你如何find两个交集。 如果您使用HashSet ，那么将您的ArrayList转换为Set s并在循环中使用retainAll()实际上是O（n）。

Answer 2

在Google Guava中还有一个静态方法Sets.intersection(set1, set2) ，返回一个不可修改的两个交集的视图。

Answer 3

接受的答案就好了; 作为更新：自Java 8以来，find两个Set的交集有一个更有效的方法。

 Set<String> intersection = set1.stream() .filter(set2::contains) .collect(Collectors.toSet()); 

之所以稍微有效率，是因为原来的方法必须添加set1元素，如果它们不在set2 ，它必须再次删除。 这种方法只会增加结果集中需要的内容。

严格地说，你可以在Java 8之前完成这个工作，但是如果没有Stream的话，代码将会变得相当麻烦。

如果两组的大小差别很大，则您最好select较小的一组。

Answer 4

还有一个想法 – 如果你的arrays/集合是不同的大小，从最小的开始是有意义的。

Answer 5

最好的select是使用HashSet来存储这些列表的内容而不是ArrayList。 如果可以，可以创build一个临时HashSet，添加要交叉的元素（使用putAll（..）方法）。 是否tempSet.retainAll（storedSet）和tempSet将包含交集。

Answer 6

您可以使用单个HashSet。 它的add（）方法返回false时，对象是集合中的。 添加列表中的对象和标记虚假返回值的计数将使您在直方图的集合+数据中获得联合（并且具有计数+ 1等于列表计数的对象是您的交集）。 如果您将计数投入TreeSet，则可以尽早检测到空的交叉点。

Answer 7

对它们进行sorting（n lg n），然后执行二进制search（lg n）。