La intersección de dos matrices ordenadas

Question

Dadas dos matrices ordenadas: A y B. El tamaño de la matriz A es La y el tamaño de la matriz B es Lb. ¿Cómo encontrar la intersección de A y B?

Si La es mucho más grande que Lb, ¿habrá alguna diferencia para el algoritmo de búsqueda de intersección?

Answer 1

Use set_intersection como here. La implementación habitual funcionaría de forma similar a la parte de combinación del algoritmo de combinación de clasificación.

Answer 2

Dado que esto parece un HW ... te voy a dar el algoritmo:

Let arr1,arr2 be the two sorted arrays of length La and Lb. 
Let i be index into the array arr1. 
Let j be index into the array arr2. 
Initialize i and j to 0. 

while(i < La and j < Lb) do 

    if(arr1[i] == arr2[j]) { // found a common element. 
     print arr[i] // print it. 
     increment i // move on. 
     increment j 
    } 
    else if(arr1[i] > arr2[j]) 
     increment j // don't change i, move j. 
    else 
     increment i // don't change j, move i. 
end while 

Answer 3

void Intersect() 
{ 
    int la, lb; 
    la = 5; 
    lb = 100; 
    int A[5]; 
    int i, j, k; 
    i = j = k = 0; 
    for (; i < 5; ++i) 
     A[i] = i + 1; 
    int B[100]; 
    for (; j < 100; ++j) 
     B[j] = j + 2; 
    int newSize = la < lb ? la : lb; 
    int* C = new int[newSize]; 
    i = j = 0; 
    for (; k < lb && i < la && j < lb; ++k) 
    { 
     if (A[i] < B[j]) 
      i++; 
     else if (A[i] > B[j]) 
      j++; 
     else 
     { 
      C[k] = A[i]; 
      i++; 
      j++; 
     } 
    } 
    for (k = 0; k < newSize; ++k) 
     cout << C[k] << NEWLINE; 
} 

Answer 4

He estado luchando con el mismo problema desde hace un tiempo, hasta el momento me vinieron con:

1. Coincidencia lineal que arrojará O (m + n) en el peor de los casos. Básicamente, mantienes dos punteros (A y B) cada uno apuntando al comienzo de cada matriz. A continuación, avance el puntero que apunta a un valor más pequeño, hasta llegar al final de uno de los arreglos, que indicaría que no hay intersección. Si en algún momento tiene * A == * B - aquí viene su intersección.

2. Coincidencia binaria. Que produce ~ O (n * log (m)) en el peor de los casos. Básicamente, eliges una matriz más pequeña y realizas una búsqueda binaria en una matriz más grande de todos los elementos de la matriz más pequeña. Si quieres ser más elegante, incluso puedes usar la última posición donde falló la búsqueda binaria y usarla como punto de partida para la próxima búsqueda binaria. De esta forma, mejora marginalmente el peor de los casos, pero para algunos conjuntos podría hacer milagros :)

3. Doble coincidencia binaria. Es una variación de la coincidencia binaria regular. Básicamente, obtienes elementos del centro de una matriz más pequeña y realizas búsquedas binarias en una matriz más grande. Si no encuentra nada, recorte la matriz más pequeña a la mitad (y sí, puede tirar el elemento que ya utilizó) y corte una matriz más grande a la mitad (use el punto de falla de búsqueda binaria). Y luego repite para cada par. Los resultados son mejores que O (n * log (m)) pero soy demasiado perezoso para calcular lo que son.

Esas son las dos más básicas. Ambos tienen méritos. Linear es un poco más fácil de implementar. El binario uno es posiblemente más rápido (aunque hay muchos casos en que la coincidencia lineal superará al binario).

Si alguien sabe algo mejor que eso, me encantaría escucharlo. Las matrices coincidentes es lo que hago en estos días.

P.S. no me cite en términos de "concordancia lineal" y "concordancia binaria" ya que los inventé yo mismo y probablemente ya tenga un nombre de fantasía.

Answer 5

//intersection of two arrays 
#include<iostream> 
using namespace std; 
int main() { 

int i=0,j=0,m,n; 
int arr1[i],arr2[j]; 
cout<<"Enter the number of elements in array 1: "; 
cin>> m; 
cout<<"Enter the number of elements in array 2: "; 
cin>>n; 
for (i=0;i<m;i++){ 
    cin>> arr1[i]; 
} 
for(j=0;j<n;j++){ 
    cin>> arr2[j]; 
} 
for(j=0;j<n;j++){ 
    for(i=0;i<m;i++) { 
     if (arr1[i] == arr2[j]){ 
     cout<< arr1[i]; 
     cout << ' '; 
     break; 
     } 
    } 
}  

return 0; 
} 

Answer 6

Vamos a considerar dos conjuntos ordenados: -

int[] array1 = {1,2,3,4,5,6,7,8}; 
int[] array2 = {2,4,8}; 

int i=0, j=0; //taken two pointers 

Mientras bucle se ejecutará hasta que ambos punteros llegan hasta las respectivas longitudes.

while(i<array1.length || j<array2.length){ 
    if(array1[i] > array2[j])  //if first array element is bigger then increment 2nd pointer 
     j++; 
    else if(array1[i] < array2[j]) // same checking for second array element 
     i++; 
    else {       //if both are equal then print them and increment both pointers 
     System.out.print(a1[i]+ " "); 

     if(i==a1.length-1 ||j==a2.length-1) //one additional check for ArrayOutOfBoundsException 
      break; 
     else{ 
      i++; 
      j++; 
     } 
    } 
}   

salida será: -

2 4 8