«1. Обзор

В этом кратком руководстве мы рассмотрим, как вычислить пересечение между двумя массивами целых чисел «a» и «b».

Мы также сосредоточимся на том, как обрабатывать повторяющиеся записи.

Для реализации мы будем использовать потоки.

2. Предикат принадлежности к массиву

Пересечение двух множеств по определению представляет собой множество со всеми значениями из одного, которые также являются частью второго множества.

Поэтому нам нужна функция или, скорее, предикат, чтобы определить членство во втором массиве. Так как List предоставляет такой метод из коробки, мы преобразуем его в список: 

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

3. Построение пересечения

Чтобы построить результирующий массив, мы рассмотрим элементы первого установите последовательно и проверьте, содержатся ли они также во втором массиве. Затем мы создадим новый массив на основе этого.

Stream API предоставляет нам необходимые методы. Сначала мы создадим поток, затем отфильтруем с помощью предиката членства и, наконец, создадим новый массив: 

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

4. Повторяющиеся записи

Поскольку массивы в Java не являются реализацией Set, мы сталкиваемся выдача повторяющихся записей во входе и потом в результате. Обратите внимание, что количество вхождений в результате зависит от вхождений в первом параметре.

Но для наборов элементы не должны встречаться несколько раз. Мы можем заархивировать это, используя метод different(): 

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

Таким образом, длина пересечения больше не зависит от порядка параметров.

Однако пересечение массива с самим собой может снова не быть массивом, поскольку мы удаляем двойные записи.

5. Пересечение мультимножеств

Более общее понятие, которое допускает несколько одинаковых записей, — это мультимножества. Для них пересечение затем определяется минимальным количеством входных вхождений. Таким образом, наш предикат членства должен вести учет того, как часто мы добавляем элемент к результату.

Для этого можно использовать метод remove(), который возвращает членство и потребляет элементы. Таким образом, после того, как все равные элементы в «b» использованы, к результату больше не добавляются равные элементы: 

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

Поскольку API массивов возвращает только неизменяемый список, мы должны сгенерировать специальный изменяемый список.

6. Заключение

В этой статье мы увидели, как использовать методы contains и remove для реализации пересечения двух массивов в Java.

Все реализации, фрагменты кода и тесты можно найти в нашем репозитории GitHub — это проект на основе Maven, поэтому его легко импортировать и запускать как есть.