logo标签列表

Java中如何高效地求两个List<String>的交集？

javalistintersection
83
问题很简单：
我有两个列表。
List<String> columnsOld = DBUtils.GetColumns(db, TableName);
List<String> columnsNew = DBUtils.GetColumns(db, TableName);

我需要获取它们的交集。有没有快速实现这个的方法？

1
@JohnnyCoder 真的吗？ - Pentium10
@Ungeheuer，如果您希望仅在两个列表中都存在时包括重复项，则该方法无效。 - xeruf
9个回答
129

您可以使用retainAll方法：

columnsOld.retainAll (columnsNew);
14
注意：如果要使此方法适用于除String之外的其他对象，则需要实现equals和hashCode方法。 - Benoit Duffez
1
代码很简单，但算法复杂度很差：O(n×m)，而集合版本的复杂度为O(n+m)。对于两个200万项的列表，这意味着进行万亿次操作和百万次操作之间的巨大差异。 - John Kugelman
如果在列表上使用retainAll，它的运行时间为O(n^2)。 - razor
28

使用 Google 的 Guava 库：

Sets.intersection(Sets.newHashSet(setA), Sets.newHashSet(setB))

注意：这种方法比简单地对两个列表求交集要高效得多：时间复杂度为O(n+m)，而使用列表版本的时间复杂度为O(n×m)。当处理两个拥有200万项目的列表时，这意味着数百万次操作与数万亿次操作之间的差别。

20

由于retainAll不会操作参数集合，因此这样做会更快：

List<String> columnsOld = DBUtils.GetColumns(db, TableName); 
List<String> columnsNew = DBUtils.GetColumns(db, TableName); 

for(int i = columnsNew.size() - 1; i > -1; --i){
    String str = columnsNew.get(i);
    if(!columnsOld.remove(str))
        columnsNew.remove(str);
}

交集将是columnsNew中剩余的值。从columnsOld中删除已经比较过的值将减少需要进行的比较次数。

但是你的代码肯定应该被提取到一个新的单独方法中，因为从这段代码中绝对不清楚它在做什么。并且我也不会拒绝为这段代码编写额外的单元测试。 - Roman
同意，良好的方法分离、命名和单元测试始终是第一原则。 - bjornhol
这个方法不应该将在columnsOld中找不到的元素添加到columnsNew中吗？看起来这些元素将会在结果中丢失。 - Calon
从columnsOld中删除列的优化实际上可能没有任何区别（删除本身是有成本的），甚至在像ArrayList这样的情况下，删除会导致元素移动而变得更慢。 - Bogdan Calmac
8

你能行吗？

private List<String> intersect(List<String> A, List<String> B) {
    List<String> rtnList = new LinkedList<>();
    for(String dto : A) {
        if(B.contains(dto)) {
            rtnList.add(dto);
        }
    }
    return rtnList;
}
7
如果B包含A中没有的元素，就没有必要遍历这些元素，因为我们试图找到A和B中全部的元素。 - juan2raid
这是O(n^2)！你应该在Set上使用contains。 - razor
4

如果不关心出现次数，可以使用retainAll；否则使用N.intersection。

a = N.asList(12, 16, 16, 17, 19);
b = N.asList(16, 19, 107);
a.retainAll(b); // [16, 16, 19]
N.println(a);

a = N.asList(12, 16, 16, 17, 19);
b = N.asList(16, 19, 107);
a = N.intersect(a, b);
N.println(a); // [16, 19]

N是abacus-common中的一个实用类。

3

使用流（Streams）有一种很好的方法可以在一行代码中完成此操作，您可以使用两个不同类型的列表，而这是使用containsAll方法无法实现的。

columnsOld.stream().filter(c -> columnsNew.contains(c)).collect(Collectors.toList());

不同类型列表的示例。如果foo和bar之间存在关系，并且您可以从foo获取bar对象，则可以修改流：

List<foo> fooList = new ArrayList<>(Arrays.asList(new foo(), new foo()));
List<bar> barList = new ArrayList<>(Arrays.asList(new bar(), new bar()));

fooList.stream().filter(f -> barList.contains(f.getBar()).collect(Collectors.toList());
2
c -> columnsNew.contains(c) 这个 lambda 表达式可以更简洁地重写为方法引用：columnsNew::contains。 - Bass
1
这不会以O(n^2)的时间运行吗？ - Aaron_H
这是O(n^2)！你应该在Set上使用contains。 - razor
3

如果你把第二个列表放在一个集合中，比如HashSet。然后遍历第一个列表，检查是否存在于集合中并在不存在时进行删除，最终你将得到所需的交集。

这种方法比在列表上使用retainAll或contains要快得多。

重点是要使用集合而不是列表。查找的时间复杂度为O(1)。

firstList.retainAll(new HashSet(secondList))也可以达到同样的效果。

1
使用 org.apache.commons.collections4.ListUtils#intersection。
0

使用 Java 8 Stream API（以及 Java 9 List.of()）可以做到以下几点：

List<Integer> list1 = List.of(1, 1, 2, 2);
List<Integer> list2 = List.of(2, 2, 3, 3);

List<Integer> intersection = list1.stream()
    .filter(list2::contains)
    .distinct()
    .collect(Collectors.toList());
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接