Перетин між двома цілими масивами

1. Огляд

У цьому короткому посібнику ми розглянемо, як обчислити перетин між двома цілими масивами 'a' та 'b' .

Ми також зупинимося на тому, як обробляти повторювані записи.

Для реалізації ми будемо використовувати Streams.

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

Перетин двох множин за визначенням є множиною з усіма значеннями з одного, які також є частиною другого множини.

Тому нам потрібна функція, а точніше предикат, щоб вирішити приналежність до другого масиву. Оскільки List надає такий метод нестандартно, ми перетворимо його на List :

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

3. Побудова перетину

Щоб створити отриманий масив, ми розглянемо елементи першого набору послідовно та перевіримо, чи містяться вони також у другому масиві.Тоді ми створимо новий масив на основі цього.

Потік API надає нам необхідні методи. Спочатку ми створимо потік , потім фільтруємо за допомогою членства - предикат і, нарешті, створимо новий масив:

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); } 

Оскільки API Arrays повертає лише незмінний Список, ми повинні створити присвячений змінний.

6. Висновок

У цій статті ми побачили, як використовувати методи містять і видаляють для реалізації перетину для двох масивів у Java.

Всю реалізацію, фрагменти коду та тести можна знайти у нашому сховищі GitHub - це проект на основі Maven, тому його слід легко імпортувати та запускати як є.