1. Обзор
В этом кратком руководстве мы рассмотрим, как вычислить пересечение двух массивов целых чисел «a» и «b» .
Мы также сосредоточимся на том, как обрабатывать повторяющиеся записи.
Для реализации мы будем использовать Streams.
2. Предикат членства для массива
Пересечение двух множеств по определению представляет собой множество со всеми значениями из одного, которые также являются частью второго множества.
Поэтому нам нужна функция или, скорее, предикат для определения членства во втором массиве. Поскольку List предоставляет такой метод из коробки, мы преобразуем его в List :
Predicate isContainedInB = Arrays.asList(b)::contains;
3. Строительство перекрестка
Чтобы построить результирующий массив, мы последовательно рассмотрим элементы первого набора и проверим, содержатся ли они также во втором массиве. `` Затем мы создадим новый массив на основе этого.
Stream API предоставляет нам необходимые методы. Во- первых, мы создадим Stream , затем отфильтруем с помощью Member - Predicate и, наконец, создадим новый массив:
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);
}
Поскольку Arrays API возвращает только неизменяемый список, мы должны создать специальный изменяемый список.
6. Заключение
В этой статье мы увидели, как использовать методы contains и remove для реализации пересечения двух массивов в Java.
Всю реализацию, фрагменты кода и тесты можно найти в нашем репозитории GitHub — это проект на основе Maven, поэтому его легко импортировать и запускать как есть.