Java中两个数组的交集

1. 概述

在这个快速教程中，我们将了解如何计算两个整数数组‘a’和’b’之间的交集。

我们还将关注如何处理重复条目。

对于实现，我们将使用Streams。

2. 数组的隶属谓词

根据定义，两个集合的交集是具有来自一个集合的所有值的集合，它们也是第二个集合的一部分。

因此，我们需要一个Function或更确切地说是一个Predicate来决定第二个数组中的成员资格。由于 List 提供了这种开箱即用的方法，我们将其转换为List：

Predicate isContainedInB = Arrays.asList(b)::contains;

3. 建立交集

为了构建结果数组，我们将依次考虑第一个集合的元素并验证它们是否也包含在第二个数组中。然后我们将基于此创建一个新数组。

Stream API 为我们提供了所需的方法。首先，我们将创建一个Stream ，然后使用members-Predicate进行过滤，最后我们将创建一个新数组：

public static Integer[] intersectionSimple(Integer[] a, Integer[] b){
    return Stream.of(a)
      .filter(Arrays.asList(b)::contains)
      .toArray(Integer[]::new);
}

4. 重复条目

由于 Java 中的数组没有Set实现，因此我们面临输入和结果中重复条目的问题。请注意，结果中出现的次数取决于第一个参数中的出现次数。

但是对于集合，元素不能多次出现。*我们可以使用*distinct()方法将其归档：

public static Integer[] intersectionSet(Integer[] a, Integer[] b){
    return Stream.of(a)
      .filter(Arrays.asList(b)::contain)
      .distinct()
      .toArray(Integer[]::new);
}

所以交点的长度不再取决于参数顺序。

但是，由于我们删除了双条目，因此数组与其自身的交集可能不再是数组。

5. 多集交集

允许多个相等条目的更一般的概念是多重集。对他们来说，交集然后由输入出现的最小数量定义。因此，我们的成员资格-*Predicate *必须记录我们向结果中添加元素的频率。

*remove()方法可用于此，它返回成员资格并使用元素。所以在‘b’*中所有相等的元素都被消耗完之后，不再有相等的元素被添加到结果中：

public static Integer[] intersectionSet(Integer[] a, Integer[] b){
    return Stream.of(a)
      .filter(new LinkedList<>(Arrays.asList(b))::remove)
      .toArray(Integer[]::new);
}

由于Arrays API 只返回一个不可变列表，我们必须生成一个专用的可变列表。