一尘不染

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

java

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

目前,仅考虑我的解决方案,看起来我应该具有Θ(n 2)的渐近运行时间。

谢谢你的帮助!

切碎

编辑:澄清一下,我真的只是想知道是否有一种更快的方法。快于Θ(n 2)。


阅读 176

收藏
2020-09-08

共1个答案

一尘不染

Set.retainAll()是找到两个集合的交集的方法。如果使用HashSet,则将ArrayLists
转换为Sets并retainAll()在所有它们中循环使用实际上是O(n)。

2020-09-08