有效地找到可变数量的字符串集的交集

Question

我有一个可变数量的ArrayList,我需要找到它的交集.字符串数量的实际上限可能在35左右,但可能更多.我不想要任何代码,只需要有效的想法.我有一个实现,我即将开始编码,但想听听其他一些想法.

目前,只是考虑我的解决方案,看起来我应该有Θ(n ²)的渐近运行时间.

谢谢你的帮助!

tshred

编辑:为了澄清,我真的只是想知道是否有更快的方法来做到这一点.比Θ(n ²)快.

Answer 1

Set.retainAll()是你如何找到两组的交集.如果您使用HashSet,那么将您的ArrayLists 转换为Sets并retainAll()在所有这些中使用循环实际上是O(n).

Answer 2

接受的答案很好; 作为更新:从Java 8开始,有一种更有效的方法来查找两个Sets 的交集.

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

它效率稍高的原因是因为原始方法必须添加set1它的元素,然后如果它们不在,则必须再次删除set2.这种方法只会在结果集中添加需要的内容.

严格地说,你也可以在Java 8之前做到这一点,但没有Streams,代码会更加费力.

如果两个组的大小差异很大,则您希望在较小的组上进行流式传输.

请注意，较小的流没有流。这是因为流的一个被迭代，而另一个（更大）的集被搜索（通过哈希搜索一个“ HashSet”，即[O（1）]（/sf/ask/460244151/查找复杂度））。 (4认同)

Answer 3

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

Answer 4

还有一个主意-如果阵列/集合的大小不同，则从最小的数组开始是有意义的。