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

intersection java set big-o theory

2022-09-01 00:47:15

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

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

感谢您的任何帮助！

tshred

编辑：为了澄清，我真的只是想知道是否有更快的方法来做到这一点。比 Θ（n^2）快。

答案 1

Set.retainAll（） 是查找两个集合的交集的方法。如果你使用，那么将 s 转换为 s 并在循环中使用所有这些实际上是 O（n）。HashSetArrayListSetretainAll()

答案 2

接受的答案很好;作为更新：从Java 8开始，有一种稍微更有效的方法来找到两个s的交集。Set

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

它稍微更有效的原因是，原始方法必须添加其中的元素，然后如果它们不在中，则必须再次删除。这种方法只会在结果集中增加需要包含的内容。set1set2

严格来说，在Java 8之前你也可以这样做，但是如果没有s，代码会更加费力。Stream

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