1. Обзор
В этом кратком руководстве мы рассмотрим, как вычислить пересечение между двумя целочисленными массивами ‘a’ и ‘b’ .
Мы также сосредоточимся на том, как обрабатывать повторяющиеся записи.
Для реализации мы будем использовать Потоки.
2. Предикат членства для массива
Пересечение двух наборов по определению является набором со всеми значениями из одного, которые также являются частью второго набора.
Поэтому нам нужна Функция или, скорее, Предикат для определения принадлежности ко второму массиву. Поскольку List предоставляет такой метод из коробки, мы преобразуем его в List :
Predicate isContainedInB = Arrays.asList(b)::contains;
Поэтому нам нужна || Функция || или, скорее, || Предикат || для определения принадлежности ко второму массиву. Поскольку || List || предоставляет такой метод из коробки, мы преобразуем его в || List ||:
Чтобы построить результирующий массив, мы последовательно рассмотрим элементы первого набора и проверим, содержатся ли они также во втором массиве. Затем мы создадим новый массив на основе этого.
API Stream предоставляет нам необходимые методы. Сначала мы создадим Поток , затем отфильтруем с помощью предиката членства – и , наконец, создадим новый массив:
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. Пересечение множества
Более общим понятием, которое допускает несколько равных записей, являются мультимножества. Для них пересечение затем определяется минимальным числом входных вхождений. Таким образом, наше членство- Предикат должно учитывать, как часто мы добавляем элемент в результат.
Для этого можно использовать метод 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, поэтому его должно быть легко импортировать и запускать как есть.