Dadas dos matrices ayb. Encuentre todos los pares de elementos (a1, b1) tales que a1 pertenece a la matriz A y b1 pertenece a la matriz B cuya sum a1 + b1 = k

Estoy buscando la solución del siguiente algoritmo con una mínima complejidad de tiempo y espacio.

Dadas dos matrices ayb, encuentre todos los pares de elementos (a1, b1) tales que a1 pertenece a la matriz A y b1 pertenece a la matriz B cuya sum a1 + b1 = k (cualquier entero).

Pude encontrar el enfoque O (n log n) donde ordenaremos uno de la matriz, digamos A, y para cada uno de los elementos b en la matriz B, realizamos la búsqueda binaria en la matriz ordenada A para el valor (Kb).

¿Podemos mejorarlo más?

Si tienes un límite en el número máximo posible (llamémoslo M) entonces puedes tener una solución en O (M + n).

Arreglo booleano de falso y marque como verdadero todo el valor para el elemento de A. Luego, para cada elemento b de B, verifique si el número de elemento Kb está marcado como verdadero.

Puede mejorarlo si está usando un hash-map en lugar de una gran matriz. Pero no consideraría que en este tipo de preguntas, hash-map es una especie de trampa.

De todos modos, le daría O (n) para la inserción y luego O (n) para la consulta, O (n) en total.

EDITAR:

Un caso donde esto podría ser útil.

  • Tiene vectores no ordenados de tamaño 10 ^ 6, por lo que ordenarlos y hacer la coincidencia es en O (n log n) con n = 10 ^ 6.
  • Necesita hacer esta operación 10 ^ 6 veces (diferentes vectores), complejidad de O (n * n * log n).
  • El valor máximo es 10 ^ 9.

Utilizar mi idea no con boolean sino con enteros (incrementada en cada ejecución) le da una complejidad de:

  • “O (10 ^ 9)” para crear la matriz (también la misma complejidad de espacio)
  • O (n) en cada ejecución, entonces O (n * n) para el total.

¡Estás utilizando más espacio, pero has aumentado la velocidad en un factor log (n) ~ = 20 en este caso!

Si las matrices están ordenadas, puede hacerlo en tiempo lineal y almacenamiento constante.

  • Comience con dos punteros, uno apuntando al elemento más pequeño de A, el otro apuntando al elemento más grande de B.
  • Calcule la sum de los elementos apuntados.
  • Si es menor que k, incremente el puntero en A para que apunte al siguiente elemento más grande.
  • Si es mayor que k, disminuya el puntero en B para que apunte al siguiente elemento más pequeño.
  • Si es exactamente k, has encontrado un par. Mueva uno de los punteros y continúe buscando el siguiente par.

Si las matrices no están ordenadas inicialmente, primero puede ordenarlas y luego usar el algoritmo anterior. Existen algunos enfoques diferentes para clasificarlos que podría usar, según el tipo de datos que espere:

  • Una clasificación de comparación, por ejemplo, Mergesort o Timsort .
  • Contando ordenar
  • Radix tipo .

Una clasificación de comparación requerirá O (n log n) tiempo en promedio. Los dos últimos son más rápidos que O (n log (n)) pero pueden ser poco prácticos si el rango de valores posibles en las matrices de entrada es muy grande.

Yo crearía una tabla hash que contiene los elementos de una matriz, luego iteraré la otra matriz buscando k - a(n) , generando un elemento de salida si la búsqueda tuvo éxito. Esto usará O (n) espacio y tiempo.

En C #, podría verse así:

 var bSet = new HashSet(B); var results = from a in A let b = k - a where bSet.Contains(b) select new { a, b }; 
 template< typename T > std::vector< std::pair< T, T > > find_pairs( std::vector< T > const & a, std::vector< T > const & b, T const & k ) { std::vector< std::pair< T, T > > matches; std::sort( a.begin(), a.end() ); // O( A * lg A ) std::sort( b.begin(), b.end() ); // O( B * lg B ) typename std::vector< T >::const_iterator acit = a.begin(); typename std::vector< T >::const_reverse_iterator bcit = b.rbegin(); for( ; acit != a.end(); /* inside */ ) { for( ; bcit != b.rend(); /* inside */ ) { const T sum = *acit + *bcit; if( sum == k ) { matches.push_back( std::pair< T, T >( *acit, *bcit ) ); ++acit; ++bcit; } else if( sum < k ) { ++acit; } else { // sum > k ++bcit; } } } // O( A + B ) return matches; } 

Utilicé C ++ y pareció darme el resultado deseado. Espero que esto sea lo que estabas buscando.

 using namespace std; using data=std::pair; void search_pairs(std::vector& A, std::vector& B, const int total, std::vector& output){ std::sort(A.begin(),A.end(),[](const int i,const int j)->bool{return (ibool{return (a* minV(nullptr); std::vector* maxV(nullptr); if(A.size()>B.size()) {minV=&B;maxV=&A;} else {minV=&A;maxV=&B;} for(auto&& itr:(*minV) ){ auto remain(total-itr); if (std::binary_search (maxV->begin(), maxV->end(), remain)){ data d{itr,remain}; if (minV==&B) std::swap(d.first,d.second); output.push_back(d); } } if (minV==&B) std::reverse(output.begin(),output.end()); } int main() { size_t nb(0); scanf("%lu",&nb); for (size_t i=0;i A,B; for (size_t i=0;i output; search_pairs(A, B, total, output); auto itr=std::begin(output); if (itr==std::end(output)) printf("-1"); while (itr!=std::end(output)){ printf("%d %d",(*itr).first, (*itr).second); if (++itr!=std::end(output)) printf(", "); } printf("\n"); } //code return 0; }