Java中ArrayLists的交集和联合

Question

有没有办法这样做？我在寻找但却找不到任何东西.

另一个问题:我需要这些方法,所以我可以过滤文件.有些是AND过滤器和一些有OR过滤器(如在集合论),所以我需要根据所有文件进行过滤和团结/交叉持有这些文件的ArrayList.

我应该使用不同的数据结构来保存文件吗？还有什么能提供更好的运行时间吗？

Answer 1

集合(所以ArrayList也有):

col.retainAll(otherCol) // for intersection
col.addAll(otherCol) // for union

如果接受重复,请使用List实现;如果不接受,则使用Set实现:

Collection<String> col1 = new ArrayList<String>(); // {a, b, c}
// Collection<String> col1 = new TreeSet<String>();
col1.add("a");
col1.add("b");
col1.add("c");

Collection<String> col2 = new ArrayList<String>(); // {b, c, d, e}
// Collection<String> col2 = new TreeSet<String>();
col2.add("b");
col2.add("c");
col2.add("d");
col2.add("e");

col1.addAll(col2);
System.out.println(col1); 
//output for ArrayList: [a, b, c, b, c, d, e]
//output for TreeSet: [a, b, c, d, e]

Answer 2

这是一个不使用任何第三方库的简单实现.主要优点是retainAll,removeAll并且addAll是这些方法不会修改输入到方法的原始列表.

public class Test {

    public static void main(String... args) throws Exception {

        List<String> list1 = new ArrayList<String>(Arrays.asList("A", "B", "C"));
        List<String> list2 = new ArrayList<String>(Arrays.asList("B", "C", "D", "E", "F"));

        System.out.println(new Test().intersection(list1, list2));
        System.out.println(new Test().union(list1, list2));
    }

    public <T> List<T> union(List<T> list1, List<T> list2) {
        Set<T> set = new HashSet<T>();

        set.addAll(list1);
        set.addAll(list2);

        return new ArrayList<T>(set);
    }

    public <T> List<T> intersection(List<T> list1, List<T> list2) {
        List<T> list = new ArrayList<T>();

        for (T t : list1) {
            if(list2.contains(t)) {
                list.add(t);
            }
        }

        return list;
    }
}

Answer 3

这篇文章相当陈旧,但它仍然是第一个在寻找该主题时在谷歌上出现的帖子.

我想使用Java 8流进行更新(基本上)在一行中执行相同的操作:

List<T> intersect = list1.stream()
    .filter(list2::contains)
    .collect(Collectors.toList());

List<T> union = Stream.concat(list1.stream(), list2.stream())
    .distinct()
    .collect(Collectors.toList());

如果有人有一个更好/更快的解决方案让我知道,但这个解决方案是一个很好的一个衬垫,可以很容易地包含在方法中,而无需添加不必要的辅助类/方法,仍然保持可读性.

Answer 4

list1.retainAll(list2) - is intersection

工会将会removeAll那么久addAll.

寻找更多的收集的文件中(的ArrayList是一个集合) http://download.oracle.com/javase/1.5.0/docs/api/java/util/Collection.html

Answer 5

联合和交叉仅为集合定义,而不是列表.如你所说.

检查番石榴库是否有过滤器.番石榴也提供真正的交叉点和工会

 static <E> Sets.SetView<E >union(Set<? extends E> set1, Set<? extends E> set2)
 static <E> Sets.SetView<E> intersection(Set<E> set1, Set<?> set2)

Answer 6

您可以使用CollectionUtils从Apache的百科全书.

Answer 7

标记的解决方案效率不高.它具有O(n ^ 2)时间复杂度.我们可以做的是对两个列表进行排序,并执行下面的交叉算法.

private  static ArrayList<Integer> interesect(ArrayList<Integer> f, ArrayList<Integer> s) { 
    ArrayList<Integer> res = new ArrayList<Integer>();

    int i = 0, j = 0; 
    while (i != f.size() && j != s.size()) { 

        if (f.get(i) < s.get(j)) {
            i ++;
        } else if (f.get(i) > s.get(j)) { 
            j ++;
        } else { 
            res.add(f.get(i)); 
            i ++;  j ++;
        }
    }


    return res; 
}

这个具有O(n log n + n)的复杂度,其为O(n log n).工会以类似的方式完成.只需确保在if-elseif-else语句中进行适当的修改.

如果你愿意,你也可以使用迭代器(我知道它们在C++中效率更高,我不知道在Java中是否也是如此).

Answer 8

从JAVA 8开始的单行代码

联盟

如果没有重复项：

  return concat(a.stream(), b.stream()).collect(toList());

联合和不同：

  return concat(a.stream(), b.stream()).distinct().collect(toList());

联合和不同如果集合/集返回类型：

  return concat(a.stream(), b.stream()).collect(toSet());

相交

如果没有重复项：

  return a.stream().filter(b::contains).collect(toList());

性能：如果集合b很大并且不是 O(1)，则通过在之前添加 1 行来预优化过滤器性能return： 复制到HasSet ( import java.util.Set;)：

... b = Set.copyOf(b);

相交和相异：

  return a.stream().distinct().filter(b::contains).collect(toList());

- 进口

导入静态java.util.stream.Stream.concat；
导入静态java.util.stream.Collectors.toList；
导入静态java.util.stream.Collectors.toSet；