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

Question

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

目前，只要考虑我的解决方案，看起来我应该有一个 Θ(n ² ) 的渐近运行时间。

谢谢你的帮助！

切丝

编辑：澄清一下，我真的只是想知道是否有更快的方法来做到这一点。^{比 Θ(n 2} )快。

score 59 · Accepted Answer

Set.retainAll()是你如何找到两个集合的交集。如果你使用HashSet，那么将你ArrayList的 s 转换为Sets 并retainAll()在所有这些上循环使用实际上是 O(n)。

score 36 · Accepted Answer

接受的答案很好；作为更新：从 Java 8 开始，有一种更有效的方法可以找到两个Sets 的交集。

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

它稍微高效的原因是因为原始方法必须添加它的元素，set1然后如果它们不在set2. 这种方法只会将需要在其中的内容添加到结果集中。

严格来说，您也可以在 Java 8 之前执行此操作，但如果没有Streams，代码会更加费力。

如果两组的大小差异很大，则您更喜欢流式传输而不是较小的一组。

score 18 · Accepted Answer

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

score 6 · Accepted Answer

6

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

于 2010-05-17T19:20:13.783 回答

score 3 · Accepted Answer

最好的选择是使用 HashSet 而不是 ArrayList 来存储这些列表的内容。如果你能做到这一点，你可以创建一个临时的 HashSet，向其中添加要相交的元素（使用 putAll(..) 方法）。做 tempSet.retainAll(storedSet) 和 tempSet 将包含交集。

score 0 · Accepted Answer

0

对它们进行排序（n lg n），然后进行二进制搜索（lg n）。

于 2010-05-17T19:10:50.910 回答

score 0 · Accepted Answer

您可以使用单个 HashSet。当对象已经在集合中时，它的 add() 方法返回 false。从列表中添加对象并标记错误返回值的计数将为您提供集合中的联合 + 直方图数据（并且 count+1 等于列表计数的对象是您的交集）。如果将计数扔给 TreeSet，则可以及早检测到空交叉点。

score 0 · Accepted Answer

如果需要状态，如果 2 集有交集，我使用 Java 8+ 版本代码的下一个片段：

set1.stream().anyMatch(set2::contains)

8 回答 8