c++ - que - Algoritmo para encontrar si dos conjuntos se cruzan
programa que haga las operaciones de conjuntos en java (7)
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], entonces muévete a ArrayA [1]. Si ArrayA [0] es más que ArrayB [0], entonces muévase a ArrayB [1].
Sigue caminando hasta llegar al final de una matriz o encuentra una coincidencia.
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 realizar una búsqueda binaria en ArrayB. Creo que esta complejidad es O (m * log n).
Debido a que ambas matrices están ordenadas, parece que debería haber un algoritmo más eficiente.
También me gustaría una solución genérica que no suponga que los arreglos contienen números (es decir, la solución también debería funcionar para cadenas). Sin embargo, los operadores de comparación están bien definidos y ambas matrices están ordenadas de menor a mayor.
Haga de cuenta 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();
}
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 se establece desde la otra lista (costo de tiempo = O (N)). 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.
Si está utilizando C # 3.0, ¿por qué no aprovechar LINQ aquí?
ArrayA.Intersect(ArrayB).Any()
No solo es genérico (funciona para cualquier tipo comparable) la implementación bajo el capó es bastante eficiente (usa un algoritmo hash).
Si no le importa el consumo de memoria, puede lograr un buen rendimiento usando hash, es decir, crear hash con claves = valores de una matriz, y valores de prueba de la segunda matriz contra este hash.
Desde 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();
esto se ejecuta en O (m + n) tiempo, pero requiere almacenar todos los duplicados y no se detiene cuando encuentra el primer dup.
Ahora, modificando el código de la implementación gnu 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;
}
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. Un documento que he encontrado en mis propias búsquedas es: