Как получить пересечение между двумя массивами как новый массив?

Я столкнулся с этой проблемой много раз в различных ситуациях. Он является общим для всех языков программирования, хотя мне нравится C или Java.

Рассмотрим два массива (или коллекции):

char[] A = {'a', 'b', 'c', 'd'}; char[] B = {'c', 'd', 'e', 'f'}; 

Как получить общие элементы между двумя массивами как новый массив? В этом случае пересечение массива A и B является char[] c = {'c', 'd'} .

Я хочу избежать повторной итерации одного массива внутри другого массива, что увеличит время выполнения на (длина A раз длины B), что слишком велико в случае огромных массивов.

Есть ли способ сделать один проход в каждом массиве, чтобы получить общие элементы?

Так как это выглядит мне как строковый алгоритм, я на мгновение предположим, что его невозможно отсортировать (следовательно, строку), тогда вы можете использовать алгоритм Longest Common Sequence (LCS)

Предполагая, что размер ввода является постоянным, проблема имеет сложность O (nxm), (длина двух входов)

 foreach element e in array A insert e into hash table H foreach element e in array B if H contains e print e 

Этот алгоритм O(N) во времени и O(N) в пространстве.

Чтобы избежать лишнего пространства, вы можете использовать подход, основанный на сортировке.

Нижняя граница эффективности – O (n) – вам нужно хотя бы прочитать все элементы. Затем есть несколько утверждений:

Тупой простейший подход

Найдите каждый элемент из массива один в массиве два. Сложность времени O (n ^ 2).

Сортировочный подход

Вам нужно отсортировать только один массив, а затем искать элементы из массива два, используя двоичный поиск. Сложность времени: сортировка O (nlogn), поиск O (n * logn) = O (nlogn), общий O (nlogn).

Хэш-подход

Создайте hash-таблицу из элементов массива. Поиск элементов из второй таблицы в хеш-таблице. Сложность времени зависит от hash-функции. Вы можете достичь O (1) для поиска в оптимальном случае (все элементы будут иметь другое значение hash-функции), но O (n) в худшем случае (все элементы будут иметь одно и то же значение hash-функции). Общая временная сложность: O (n ^ x), где x – коэффициент эффективности hash-функции (от 1 до 2).

Некоторые хеш-функции гарантированно создают таблицу без столкновений. Но здание больше не занимает строго O (1) времени для каждого элемента. В большинстве случаев это будет O (1), но если таблица заполнена или столкновение встречается, тогда таблица необходимо перефразировать – с учетом времени O (n). Это происходит не так часто, гораздо реже, чем чистые добавки. Таким образом, сложность времени AMORTIZED равна O (1). Мы не заботимся о том, чтобы некоторые из добавлений принимали O (n) время, пока большинство добавок занимает O (1) раз.

Но даже в этом случае, в крайнем случае, таблица должна быть перефразирована для каждой отдельной вставки, поэтому строгая временная сложность будет O (n ^ 2)

Есть несколько методов на некоторых языках, о которых я знаю, которые делают именно то, что вы хотите, подумали ли вы о некоторых из этих реализаций?

PHP – array_intersect ()

 $array1 = array("a" => "green", "red", "blue"); $array2 = array("b" => "green", "yellow", "red"); $result = array_intersect($array1, $array2); print_r($result); >> green red 

Java – List.retainAll

 Collection listOne = new ArrayList(Arrays.asList("milan","dingo", "elpha", "hafil", "meat", "iga", "neeta.peeta")); Collection listTwo = new ArrayList(Arrays.asList("hafil", "iga", "binga", "mike", "dingo")); listOne.retainAll( listTwo ); System.out.println( listOne ); >> dingo, hafil, iga 
  public static void main(String[] args) { char[] a = {'a', 'b', 'c', 'd'}; char[] b = {'c', 'd', 'e', 'f'}; System.out.println(intersect(a, b)); } private static Set intersect(char[] a, char[] b) { Set aSet = new HashSet(); Set intersection = new HashSet(); for (char c : a) { aSet.add(c); } for (char c : b) { if (aSet.contains(c)) { intersection.add(c); } } return intersection; } 
 int s[256] // for considering all ascii values, serves as a hash function for(int i=0;i<256;i++) s[i]=0; char a[]={'a','b','c','d'}; char b[]={'c','d','e','f'}; for(int i=0;i0) cout< 

Google Guava

На это уже много хороших ответов, но если вы хотите использовать однострочный подход с использованием библиотеки для ленивого кодирования, я бы пошел с Google Guava (для Java) и его методом Sets.intersection .

(нет компилятора под рукой, нести со мной)

 char[] A = {'a', 'b', 'c', 'd'}; char[] B = {'c', 'd', 'e', 'f'}; Set intersection = Sets.intersection( Sets.newHashSet(Chars.asList(a)), Sets.newHashSet(Chars.asList(b)) ); 

Очевидно, что это предполагает, что оба массива не будут иметь дубликатов, и в этом случае использование установленной структуры данных будет иметь больше смысла и более эффективно использовать этот вид операции, особенно если вы не начинаете с массива примитивов с самого начала ,

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

  1. Сортируйте оба массива.
  2. Затем сделайте цикл, пока они не будут иметь общие элементы. Один из массивов достигает своего конца.

Асимптотически это усложняет сортировку. т.е. O (NlogN), где N – длина более длинного входного массива.

Если вы заботитесь о дубликатах, используйте хеш-карту для индекса A, при этом ключ является элементом, а значение представляет собой количество раз, сколько раз этот элемент был замечен.

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

Затем итерации через B, и если это значение существует, вычтите 1. Если нет, поместите -1 в значение для таблицы для этого элемента.

Наконец, итерации по карте и для любого элемента, имеющего значение! = 0, распечатайте как разницу.

 private static  List intersectArrays(List a, List b) { Map intersectionCountMap = new HashMap((((Math.max(a.size(), b.size()))*4)/3)+1); List returnList = new LinkedList(); for(T element : a) { Long count = intersectionCountMap.get(element); if (count != null) { intersectionCountMap.put(element, count+1); } else { intersectionCountMap.put(element, 1L); } } for (T element : b) { Long count = intersectionCountMap.get(element); if (count != null) { intersectionCountMap.put(element, count-1); } else { intersectionCountMap.put(element, -1L); } } for(T key : intersectionCountMap.keySet()) { Long count = intersectionCountMap.get(key); if (count != null && count != 0) { for(long i = 0; i < count; i++) { returnList.add(key); } } } return returnList; } 

Это должно выполняться в O(n) , так как мы только повторяем списки каждый раз и карту один раз. Структуры данных, используемые здесь в Java, должны быть эффективными, поскольку HashMap построен с емкостью, которая может обрабатывать наибольший размер списков.

Я использую LinkedList для возврата, поскольку он предоставляет нам способ добавления и итерации через список для нашего неизвестного размера пересечения.

Лучший способ – не начинать с массивов вообще. Массивы оптимальны для случайного доступа к элементам, но не оптимальны для поиска (вот что такое пересечение). Поскольку вы говорите о пересечении , вы должны относиться к массивам как к наборам. Поэтому используйте более подходящую структуру данных (в Java, Set ). Тогда задача намного эффективнее.

Вы можете использовать дерево, но время будет O (n (log n)), и элементы должны быть сопоставимы

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

Если предоставляется дополнительное пространство, мы можем использовать хеш-таблицу для этого.

в rubyе вы можете просто сказать

 a = ['a', 'b', 'c', 'd'] b = ['c', 'd', 'e', 'f'] c = a & b 

c содержит [‘c’, ‘d’]

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

Код находится здесь:

 public static void printArr(int[] arr){ for (int a:arr){ System.out.print(a + ", "); } System.out.println(); } public static int[] intersectionOf(int[] arr1, int[] arr2){ Arrays.sort(arr1); Arrays.sort(arr2); printArr(arr1); printArr(arr2); int i=0, j=0, k=0; int[] arr = new int[Math.min(arr1.length, arr2.length)]; while( i < arr1.length && j < arr2.length){ if(arr1[i] < arr2[j]){ i++; } else if(arr1[i] > arr2[j]){ j++; } else { arr[k++] = arr1[i++]; j++; } } return Arrays.copyOf(arr, k); } public static void main(String[] args) { int[] arr1 = {1, 2, 6}; int[] arr2 = {10, 2, 5, 1}; printArr(intersectionOf(arr1,arr2)); } 

выходы:

 arr1: 1, 2, 6, arr2: 1, 2, 5, 10, arr: 1, 2, 

Предполагая, что вы имеете дело с символами ANSI. Этот подход должен быть аналогичным для Unicode, просто измените диапазон.

 char[] A = {'a', 'b', 'c', 'd'}; char[] B = {'c', 'd', 'e', 'f'}; int[] charset = new int[256] for(int i=0; i 

Теперь итерации по B, и вы можете проверить, больше ли значение соответствующей кодировки для повторяющегося символа больше 0. Вы можете сохранить их в списке или любой другой коллекции.

Этот подход требует сложности времени O (n) и постоянного пространства для ваших проверок, не принимая во внимание ваш новый массив / список, используемый для хранения общих элементов.

Это лучше, чем подход HashSet / Hashtable с точки зрения сложности пространства.

Вы можете использовать HashSet в .NET 3.5 или новее. Пример кода c #:

 HashSet set1 = new HashSet(new int[]{8, 12, 13, 15}); HashSet set2 = new HashSet(new int[] { 15, 16, 7, 8, 9 }); set1.IntersectWith(set2); foreach (int i in set1) Console.Write(i+ " "); 

// вывод: 8 15

Сортировка одного из массивов (m Log (m)) Теперь выберите каждый элемент из другого массива и выполните двоичный поиск в первом массиве (отсортированный) -> n Log (m)

Общая временная сложность: – (n + m) Log (m) .

Я надеюсь, что следующее будет полезно. К ним относятся два разных подхода:

  • Простой пересечение, где вы сравниваете все элементы из одного массива в другой массив.

  • Метод сортировки и поиска основан на сортировке одного массива и поиске второго элемента массива в первом массиве с использованием двоичного поиска.

//

 public class IntersectionOfUnsortedArrays { public static void main(String[] args) { int[] arr1 = { 12, 4, 17 }; int[] arr2 = { 1, 12, 7, 17 }; System.out.println("Intersection Using Simple Comparision"); printArray(simpleIntersection(arr1, arr2)); System.out.println("Intersection Using Sort and Binary Search"); printArray(sortingBasedIntersection(arr1, arr2)); } /* * Simple intersection based on the comparison without any sorting. * Complexity O(n^2) */ public static int[] simpleIntersection(int[] a, int[] b) { int minlen = a.length > b.length ? b.length : a.length; int c[] = new int[minlen]; int k=0; for(int i=0;i b.length ? b.length : a.length; int c[] = new int[minlen]; int k=0; for(int i=0;i -1){ c[k++] = a[result]; } } int arr[] = new int[k]; // copy the final array to remove unwanted 0's from the array c System.arraycopy(c, 0, arr, 0, k); return arr; } public static void insertionSort(int array[]) { for (int i = 1; i < array.length; i++) { int j = i; int b = array[i]; while ((j > 0) && (array[j - 1] > b)) { array[j] = array[j - 1]; j--; } array[j] = b; } } static int binarySearch(int arr[], int low, int high, int num) { if (high < low) return -1; int mid = (low + high) / 2; if (num == arr[mid]) return mid; if (num > arr[mid]) return binarySearch(arr, (mid + 1), high, num); else return binarySearch(arr, low, (mid - 1), num); } public static void printArray(int[] array) { for (int value : array) { System.out.print(" "+value); } System.out.println("\n"); } } 

Если коллекции уже отсортированы, как показано в вопросе, то лучшим решением (еще не упомянутым) является алгоритм, подобный слиянию, который работает в O (n + m).

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

Используя функции Java 8, вот алгоритм, который выполняет дублирование в списке вместо того, чтобы превращать список в набор. Нет сортировки, поэтому нет n log n .

  1. Преобразуйте один из списков в карту со значением, являющимся числом вхождений (стоимость: O (n)).
  2. Для каждого элемента в другом списке, если элемент существует на карте, уменьшите его на единицу (стоимость: O (n)).

Поэтому общая стоимость O (n). Код:

 import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Map; import java.util.stream.Collectors; public class Dup { public static void main(String[] args) { List listA = Arrays.asList(3, 1, 4, 1, 9, 5, 9); List listB = Arrays.asList(2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3); findCommons(listA, listB); } static void findCommons(List listA, List listB) { Map mapA = listA.stream().collect( Collectors.groupingBy(Integer::intValue, Collectors.counting())); List commons = new ArrayList<>(); listB.stream() .filter(e -> mapA.get(e) != null) .filter(e -> mapA.get(e) > 0) .forEach(e -> { mapA.put(e, mapA.get(e) - 1); commons.add(e); }); System.out.println(commons); } } 

Код выше даст этот результат: [5, 3, 9, 9] .

import java.util.Scanner;

public class arraycommon {

 public static void main(String[] args) { Scanner sc=new Scanner(System.in); // display common element in two diffrent array int sizea,sizeb,i=0,j=0,k=0; int count=0; System.out.println("enter the size array A:"+'\n'); sizea=sc.nextInt(); System.out.println("enter the size array B"+'\n'); sizeb=sc.nextInt(); int a[]=new int[sizea]; int b[]=new int[sizeb]; int c[]=new int[sizea]; System.out.println("enter the element in array A:"+'\n'); for (i = 0; i < sizea; i++) { a[i]=sc.nextInt(); } System.out.println("enter the element in array B:"+'\n'); for (i = 0; i < sizeb; i++) { b[i]=sc.nextInt(); } System.out.println("the element in array A:"+'\n'); for (i = 0; i < sizea; i++) { System.out.print(a[i]+" "); } System.out.println('\n'); System.out.println("the element in array B:"+'\n'); for (i = 0; i < sizeb; i++) { System.out.print(b[i]+" "); } for (i = 0; i  

}

  simply search each element of first array with each element of second array and stored matched result in third array class Union { public static void main(String[] args) { char a[] ={'f','g','d','v','a'}; char b[] ={'a','b','c','d','e'}; char temp[] = new char[5]; int p=0; for(int i=0;i 
  • Как я могу найти фактический путь, найденный BFS?
  • Получение ближайшего соответствия строк
  • Сложность времени рекурсивного алгоритма
  • Почему алгоритм Дейкстры не работает для отрицательных границ веса?
  • Перечислим все уникальные enums вектора в R
  • Создать последовательность случайных чисел без повторений
  • Поиск всех возможных комбинаций чисел для достижения заданной суммы
  • Как найти, какие элементы находятся в сумке, используя алгоритм Knapsack Algorithm ?
  • Каковы различия между деревьями сегментов, деревьями интервалов, двоичными индексированными деревьями и деревьями диапазона?
  • как растеризовать вращающийся прямоугольник (в 2d с помощью setpixel)
  • Поиск медианы несортированного массива
  • Давайте будем гением компьютера.