求两个Int数组的交集

1. Overview

In this quick tutorial, we’ll have a look at how to compute the intersection between two Integer arrays ‘a’ and ‘b’.

We’ll also focus on how to handle duplicate entries.

For the implementation, we’ll use Streams.

2. Membership Predicate for an Array

The intersection of two sets is by definition a set with all values from one, which are also part of the second set.

Therefore we need a Function or rather a Predicate to decide the membership in the second array. Since List provides such a method out of the box, we’ll transform this to a List:

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

3. Building the Intersection

To build up the resulting array, we’ll consider the elements of the first set sequentially and verify if they’re also contained in the second array. Then we’ll create a new array based on this.

The Stream API provides us with the needed methods. First, we’ll create a Stream, then filter with the membership-Predicate and finally we’ll create a new array:

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

4. Duplicate Entries

Since arrays in Java are no Set implementation, we face the issue of duplicate entries in the input and then in the result. Notice that the number of occurrences in the result depends on the occurrences in the first parameter.

But for sets, elements must not occur multiple times. We can archive this by using the distinct() method:

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

So the length of the intersection no longer depends on the parameter order.

However, the intersection of an array with itself may not be the array again since we remove double entries.

5. Multiset Intersection

A more general notion, which allows multiple equal entries, are multisets. For them, the intersection is then defined by the minimal number of input occurrences. So our membership-Predicate must keep score how often we add an element to the result.

The remove() method can be used for this, which returns the membership and consumes the elements. So after all equal elements in ‘b’ are consumed, no more equal elements are added to the result:

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

Since the Arrays API only returns an immutable List, we have to generate a dedicate mutable one.

6. Conclusion

In this article, we’ve seen how to use the contains and remove methods to implement an intersection for two arrays in Java.

All the implementation, code snippets, and tests can be found in our GitHub repository – this is a Maven-based project, so it should be easy to import and run as it is.