获取 2 个或多个嵌套 ArrayList 之间的交集的更有效方法

Question

如果我有，说单独的 3 个嵌套 ArrayLists 字符串，即 ArrayList<ArrayList<String>>:

找到它们的交集（公共元素）的最有效方法是什么？
是否有其他数据结构可以替代嵌套ArrayLists结构，提高求交集的效率？（例如，我能想到的第一个结构是使用 Set，但我想看看是否有其他建议。）

提前致谢！

Answer 1

我会使用 list.retainAll 中的方法

private ArrayList<String> getIntersection(ArrayList<ArrayList<String>> lists) {
    if(null == lists || lists.isEmpty()) {
        return null;
    }
    ArrayList<String> intersection = lists.get(0);
    lists.forEach(intersection::retainAll);
    return intersection;
}

Answer 2

两个列表的交集使用retainAll()方法完成。

它会更新列表，所以如果你不想那样，你应该先复制列表。

如果您有 2 个以上的列表，请复制第一个列表，然后为每个剩余列表调用 retainAll()。

ArrayList<ArrayList<String>> lists = ...

List<String> intersection = new ArrayList<>(lists.get(0));
for (List<String> list : lists.subList(1, lists.size()))
    intersection.retainAll(list);

但是性能会很差 O(n*m)，其中 n 和 m 是两个最大列表的大小。

这是因为 retainAll() 对参数中给定的列表执行了 contains()，这是对 intersection 列表中每个元素的顺序搜索。

通过将列表转换为集合，可以将性能提高到 O(n)，其中 n 是最大的列表。

List<String> intersection = new ArrayList<>(lists.get(0));
for (List<String> list : lists.subList(1, lists.size()))
    intersection.retainAll(new HashSet<>(list));

在 Java 8+ 中，for 循环可以简化为以下之一：

lists.subList(1, lists.size()).stream().map(HashSet::new).forEach(intersection::retainAll);

lists.subList(1, lists.size()).forEach(list -> intersection.retainAll(new HashSet<>(list)));

获取 2 个或多个嵌套 ArrayList 之间的交集的更有效方法

More efficient way to get the intersection between 2 or more nested ArrayLists

java

list

arraylist

set-intersection