Algoritmo para encontrar si dos conjuntos se cruzan

Question

Digamos que tengo dos matrices:

int Arraya [] = {5, 17, 150, 230, 285};

int ArrayB [] = {7, 11, 57, 110, 230, 250};

Ambas matrices están ordenadas y pueden ser de cualquier tamaño. Estoy buscando un algoritmo eficiente para encontrar si los arrays contienen elementos duplicados entre ellos. Solo quiero una respuesta verdadera/falsa, no me importa qué elemento se comparte o cuántos.

La solución ingenua consiste en recorrer cada elemento en ArrayA, y hacer un binary search en ArrayB. Creo que esta complejidad es O (m * log n).

Debido a que ambos conjuntos se clasifican, parece que debe haber un algoritmo más eficiente.

También me gustaría una solución genérica que no asumen que las matrices tienen números (es decir, la solución debería funcionar también para cuerdas). Sin embargo, los operadores de comparación están bien definidos y ambas matrices están ordenadas de menor a mayor.

Answer 1

Imagine que está haciendo un mergesort, pero no envíe los resultados a ningún lado. Si llega al final de cualquiera de las fuentes, no hay intersección. Cada vez que compara el siguiente elemento de cada uno, si son iguales, hay una intersección.

Por ejemplo:

counterA = 0; 
counterB = 0; 
for(;;) { 
    if(counterA == ArrayA.length || counterB == ArrayB.length) 
     return false; 
    else if(ArrayA[counterA] == ArrayB[counterB]) 
     return true; 
    else if(ArrayA[counterA] < ArrayB[counterB]) 
     counterA++; 
    else if(ArrayA[counterA] > ArrayB[counterB]) 
     counterB++; 
    else 
     halt_and_catch_fire(); 
} 

Answer 2

Si no se preocupan por el consumo de memoria, se puede lograr un buen rendimiento mediante el uso de hash, es decir, crear hash con teclado = valores de una matriz, y prueba los valores de segunda matriz contra este hash

Answer 3

Si el rango de valores es pequeño, puede crear una tabla de búsqueda para uno de ellos (costo de tiempo = O (N)) y luego verificar si el bit está establecido en la otra lista (costo de tiempo = EN)). Si el rango es grande, podría hacer algo similar con una tabla hash.

El truco de mergesort de Glomek es una idea aún mejor.

Answer 4

Glomek está en el camino correcto, pero pasó por alto el algoritmo.

Comience comparando ArrayA [0] con ArrayB [0]. si son iguales, ya terminaste. Si ArrayA [0] es menor que ArrayB [0], luego muévase a ArrayA [1]. Si ArrayA [0] es más que ArrayB [0], luego desplácese a ArrayB [1].

Manteniendo el paso hasta llegar al final de una matriz o encontrar una coincidencia.

Answer 5

Si está utilizando C# 3.0, ¿por qué no aprovechar LINQ aquí?

ArrayA.Intersect(ArrayB).Any() 

Esto no sólo es genérico (que funciona para cualquier tipo comparable) la puesta en práctica bajo el capó es bastante eficiente (utiliza un algoritmo de hash).

Answer 6

Dado que alguien se preguntó sobre stl. Fuera de la caja, el algoritmo set_intersection haría más de lo que quisiera: encontraría todos los valores comunes.

#include <vector> 
    #include <algorithm> 
    #include <iterator> 
    using namespace std; 
// ...  
     int ArrayA[] = {5, 17, 150, 230, 285}; 
     int ArrayB[] = {7, 11, 57, 110, 230, 250}; 
     vector<int> intersection; 
     ThrowWhenWritten output_iterator; 
     set_intersection(ArrayA, ArrayA + sizeof(ArrayA)/sizeof(int), 
         ArrayB, ArrayB + sizeof(ArrayB)/sizeof(int), 
         back_insert_iterator<vector<int> >(intersection)); 

     return !intersection.empty(); 

este se ejecuta en tiempo O (m + n), pero requiere el almacenamiento de todos los duplicados y no se detiene cuando encuentra la primera dup.

Ahora, modificando el código del gnu implementation del stl, podemos obtener más exactamente lo que desea.

template<typename InputIterator1, typename InputIterator2> 
bool 
has_intersection(InputIterator1 first1, InputIterator1 last1, 
      InputIterator2 first2, InputIterator2 last2) 
    { 
     while (first1 != last1 && first2 != last2) 
     { 
      if (*first1 < *first2) 
      ++first1; 
      else if (*first2 < *first1) 
      ++first2; 
      else 
      return true; 
     } 
     return false; 
} 

Answer 7

Si una lista es mucho más corta que la otra, la búsqueda binaria es el camino a seguir. Si las listas son de una longitud similar y está contento con O (m + n), una "fusión" estándar funcionaría. Hay algoritmos más elegantes que son más flexibles. Uno de los artículos que he encontrado en mis propias búsquedas es:

http://www.cs.uwaterloo.ca/~ajsaling/papers/paper-spire.pdf