¿Cómo obtengo la intersección entre dos matrices como una nueva matriz?

Enfrenté este problema muchas veces durante varias situaciones. Es genérico para todos los lenguajes de progtwigción aunque me siento cómodo con C o Java.

Consideremos dos matrices (o colecciones):

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

¿Cómo obtengo los elementos comunes entre las dos matrices como una nueva matriz? En este caso, la intersección de la matriz A y B es char[] c = {'c', 'd'} .

Quiero evitar la iteración repetida de una matriz dentro de la otra matriz, lo que boostá el tiempo de ejecución en (longitud de A veces la longitud de B), que es demasiado en el caso de las matrices de gran tamaño.

¿Hay alguna manera de que podamos hacer una sola pasada en cada conjunto para obtener los elementos comunes?

Dado que esto me parece un algoritmo de cadena, asumiré por un momento que no es posible ordenar esta secuencia (por lo tanto, cadena), entonces puede usar el algoritmo de secuencia común más larga (LCS).

Suponiendo que el tamaño de entrada es constante, entonces el problema tiene una complejidad de O (nxm), (longitud de las dos entradas)

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

Este algoritmo es O(N) en el tiempo y O(N) en el espacio.

Para evitar el espacio extra, puede usar el enfoque basado en clasificación.

El límite inferior de la eficiencia es O (n); es necesario que al menos lea todos los elementos. Luego hay varios apporaches:

Enfoque más simple tonto

Busque cada elemento de la matriz uno en la matriz dos. Complejidad del tiempo O (n ^ 2).

Enfoque de clasificación

Debe ordenar solo la matriz uno, luego buscar elementos de la matriz dos utilizando la búsqueda binaria. Complejidad del tiempo: ordenando O (nlogn), buscando O (n * logn) = O (nlogn), total O (nlogn).

Enfoque Hash

Crea una tabla hash a partir de elementos de la matriz uno. Busque los elementos de la segunda tabla en la tabla hash. La complejidad del tiempo depende de la función hash. Puede lograr O (1) para búsquedas en el caso óptimo (todos los elementos tendrán diferente valor hash), pero O (n) en el peor de los casos (todos los elementos tendrán el mismo valor hash). Complejidad del tiempo total: O (n ^ x), donde x es un factor de eficacia de la función hash (entre 1 y 2).

Algunas funciones hash están garantizadas para construir una tabla sin colisiones. Pero el edificio ya no toma estrictamente O (1) tiempo para cada elemento. Será O (1) en la mayoría de los casos, pero si la tabla está llena o se encuentra una colisión, entonces la tabla debe ser reaprovisionada, tomando O (n) el tiempo. Esto sucede no tan a menudo, y con mucha menos frecuencia que la limpieza. Entonces, la complejidad del tiempo AMORTIZADO es O (1). No nos importan algunas de las adiciones que toman el tiempo de O (n), siempre que la mayoría de las adiciones tome O (1) vez.

Pero aun así, en un caso extremo, la tabla debe ser repite cada una de las inserciones, por lo que la estricta complejidad de tiempo sería O (n ^ 2)

Hay algunos métodos en algunos idiomas de los que soy consciente que hacen exactamente lo que usted desea, ¿ha considerado examinar algunas de estas implementaciones?

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

Ya hay muchas buenas respuestas para esto, pero si quieres el enfoque de una sola línea utilizando una biblioteca para encoding diferida, Sets.intersection Google Guava (para Java) y su método Sets.intersection .

(sin comstackdor a la mano, tengan paciencia)

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

Obviamente, esto supone que ambas matrices no tendrán duplicados, en cuyo caso el uso de una estructura de datos establecida tendría más sentido y permitiría este tipo de operación de manera más eficiente, especialmente si no se inicia desde un conjunto de primitivas desde el principio. .

Puede o no ajustarse a su caso de uso, pero una especie de enfoque obvio para el caso general.

  1. Ordene ambas matrices.
  2. Luego haga un ciclo hasta que tengan elementos comunes O una de las matrices llegue a su fin.

Asintóticamente, esto requiere la complejidad de la clasificación. es decir O (NlogN) donde N es la longitud de una matriz de entrada más larga.

Si le importan los duplicados, use un mapa hash para indexar la lista A, donde la clave es el elemento y el valor es el número de veces que ese elemento se ha visto.

Usted itera a través del primer y para cada elemento en A y si no existe en el mapa, póngalo allí con un valor de 1, si ya existe en el mapa, agregue uno a ese valor.

Luego, recorra a través de B, y si el valor existe, reste 1. De lo contrario, ponga -1 en el valor de la tabla para ese elemento.

Finalmente, recorra el mapa y para cualquier elemento que tenga un valor! = 0, imprima como una diferencia.

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

Esto debería ejecutarse en O(n) , ya que solo estamos iterando las Listas una vez y el Mapa una vez. Las estructuras de datos utilizadas aquí en Java deberían ser eficientes, ya que el HashMap está construido con una capacidad que puede manejar el tamaño más grande de las listas.

Estoy usando LinkedList para la devolución ya que nos proporciona una forma de agregar e iterar a través de una lista para nuestra intersección de tamaño desconocido.

La mejor manera es no comenzar con matrices en absoluto. Las matrices son óptimas para el acceso aleatorio a los elementos, pero no son óptimas para la búsqueda (que es de lo que se trata encontrar la intersección). Como está hablando de intersección , debe considerar las matrices como conjuntos. Por lo tanto, use una estructura de datos más apropiada (en Java, un Set ). Entonces la tarea es mucho más eficiente.

Puede usar árbol, pero el tiempo será O (n (log n)) y los elementos deben ser comparables

Primero, clasifique las dos matrices utilizando el mejor algoritmo de clasificación.
Luego, con la búsqueda lineal, puede obtener los elementos comunes.

Si se proporciona un espacio adicional, entonces podemos usar la tabla hash para hacer eso.

en ruby ​​puedes decir

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

c contiene [‘c’, ‘d’]

Ordene primero dos matrices y luego itere, si son el mismo elemento, agréguelo para que se devuelva la matriz.

El código está aquí:

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

productos:

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

Suponiendo que se trata de caracteres ANSI. El enfoque debe ser similar para Unicode, simplemente cambie el rango.

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

Ahora itere sobre la B y puede verificar si el valor del juego de caracteres correspondiente para el personaje que se está iterando es mayor que 0. Puede almacenarlos en una lista o en cualquier otra colección.

Este enfoque toma O (n) la complejidad del tiempo y un espacio constante para sus cheques sin tener en cuenta su nueva matriz / lista que se utiliza para contener los elementos comunes.

Esto es mejor que el enfoque HashSet / Hashtable en términos de complejidad del espacio.

Puede usar HashSet en .NET 3.5 o posterior. Ejemplo de código 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+ " "); 

// salida: 8 15

Ordenar una de las matrices (m Log (m)) ahora Elija cada elemento de otra matriz y realice una búsqueda binaria en la primera matriz (la ordenada) -> n Log (m)

Complejidad total del tiempo: – (n + m) Log (m) .

Espero que lo siguiente sea útil. Estos son dos enfoques diferentes:

  • Intersección simple donde se comparan todos los elementos de una matriz a otra.

  • Enfoque basado en ordenamiento y búsqueda que ordena una matriz y busca el segundo elemento de la matriz en la primera matriz mediante la búsqueda binaria.

//

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

Si las colecciones ya están ordenadas, como se muestra en la pregunta, entonces la mejor solución (aún no mencionada) es un algoritmo de tipo fusión que se ejecuta en O (n + m).

Compara los primeros elementos de cada colección. Si son iguales, agregue el elemento al conjunto de intersección y muestre ambos elementos de sus colecciones. Si los elementos son diferentes, muestre el elemento que es mayor, en comparación, con el otro elemento. Repita hasta que una colección esté vacía.

Usando las características de Java 8, aquí hay un algoritmo que respeta los duplicados dentro de una lista en lugar de convertir una lista en un conjunto. Sin clasificación, así que no n log n .

  1. Convierta una de las listas en un mapa, con el valor que es el número de ocurrencias (costo: O (n)).
  2. Para cada elemento en la otra lista, si el elemento existe en el mapa, disminuya la ocurrencia en uno (costo: O (n)).

Por lo tanto, el costo total es O (n). Código:

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

El código anterior dará esta salida: [5, 3, 9, 9] .

import java.util.Scanner;

clase pública 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