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




java vs c++ diferencias (18)

  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.

Enfrenté este problema muchas veces durante varias situaciones. Es genérico para todos los lenguajes de programació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 aumentará 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?


Answer #1

Puede usar HashSet en .NET 3.5 o posterior. Ejemplo de código c #:

HashSet<int> set1 = new HashSet<int>(new int[]{8, 12, 13, 15});

HashSet<int> set2 = new HashSet<int>(new int[] { 15, 16, 7, 8, 9 });

set1.IntersectWith(set2);

foreach (int i in set1)

   Console.Write(i+ " ");

// salida: 8 15


Answer #2
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;i<sizeof(a);i++)
{
   s[a[i]]++;
 }

 for(int i=0;i<sizeof(b);i++)//checker function
 {
     if(s[b[i]]>0)
       cout<<b[i]; 
  }


  complexity O(m+n);
  m- length of array a
  n- length of array b

Answer #3
    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<a.length;i++)
  {
    for(int j=0;j<b.length;j++)
    {
      if(a[i]==b[j])     //searches if both array has common element
      {

        temp[p] = a[i];   //if match found store it in a new array
        p++;
      }

    }

  }
  for(int k=0;k<temp.length;k++)
  {
      System.out.println(temp[k]);
  }

  }
}

Answer #4

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<Integer> listA = Arrays.asList(3, 1, 4, 1, 9, 5, 9);
    List<Integer> listB = Arrays.asList(2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3);
    findCommons(listA, listB);
  }

  static void findCommons(List<Integer> listA, List<Integer> listB) {
    Map<Integer, Long> mapA = 
        listA.stream().collect(
            Collectors.groupingBy(Integer::intValue, Collectors.counting()));

    List<Integer> 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] .


Answer #5

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


Answer #6

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.


Answer #7

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)


Answer #8

Google Guava

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

(sin compilador a la mano, tengan paciencia)

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

Set<Character> intersection = Sets.intersection(
    Sets.newHashSet<Character>(Chars.asList(a)),
    Sets.newHashSet<Character>(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.


Answer #9

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.


Answer #10
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.


Answer #11

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, 

Answer #12

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 <T> List<T> intersectArrays(List<T> a, List<T> b) {
    Map<T, Long> intersectionCountMap = new HashMap<T, Long>((((Math.max(a.size(), b.size()))*4)/3)+1);
    List<T> returnList = new LinkedList<T>();
    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.


Answer #13

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<A.length; i++) {
  charset[A[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.


Answer #14

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<a.length;i++){
            for(int j=0;j<b.length;j++){
                if(a[i]==b[j]){
                    c[k++]=a[i];
                }
            }
        }
        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;
    }

    /*
     * Sorting and Searching based intersection.
     * Complexity Sorting O(n^2) + Searching O(log n)
     */

    public static int[] sortingBasedIntersection(int[] a, int[] b){
        insertionSort(a);
        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;i++){
            int result = binarySearch(a,0,a.length,b[i]);
            if(result > -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");
    }
}


Answer #15

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)


Answer #16

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

Answer #17

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





algorithm