algorithm - propiedades - producto cartesiano relaciones y funciones

Dados dos conjuntos a y b. Encuentre todos los pares de elementos(a1, b1) de manera que a1 pertenezca al conjunto A y b1 pertenezca al conjunto B, cuya suma a1+b1=k

Question

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

Dados dos matrices a y b, encuentre todos los pares de elementos (a1, b1) de manera que a1 pertenezca a la matriz A y b1 pertenezca a la matriz B, cuya suma a1 + b1 = k (cualquier entero).

Pude encontrar un enfoque O (n log n) en el que clasificaremos uno de los arreglos, por ejemplo A y para cada uno de los elementos b en el arreglo B, realizaremos una búsqueda binaria en el arreglo ordenado A para el valor (Kb).

¿Podemos mejorarlo más?

Answer 1

Me gustaría crear una tabla hash que contenga 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 };

Answer 2

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

• Comience con dos punteros, uno que apunta al elemento más pequeño de A y el otro que apunta al elemento más grande de B.
• Calcula la suma de los elementos apuntados.
• Si es más pequeño que k, incremente el puntero en A para que apunte al siguiente elemento más grande.
• Si es más grande que k, decrementa el puntero en B para que apunte al siguiente elemento más pequeño.
• Si es exactamente k has encontrado un par. Mueve uno de los punteros y sigue buscando el siguiente par.

Si las matrices inicialmente no están clasificadas, 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 espera:

• Un tipo de comparación, por ejemplo, Mergesort o Timsort .
• Contando orden
• Tipo de radix .

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.

Answer 3

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

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

Puede mejorarlo si está utilizando 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 sin clasificar de tamaño 10 ^ 6, por lo tanto, ordenarlos y hacer la comparación es en O (n log n) con n = 10 ^ 6.
• Debe realizar esta operación 10 ^ 6 veces (vectores diferentes), complejidad de O (n * n * log n).
• El valor máximo es 10 ^ 9.

Usar mi idea no con booleano sino entero (incrementado 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, así que O (n * n) para el total.

¡Está utilizando más espacio pero ha aumentado la velocidad en un registro de factores (n) ~ = 20 en este caso!

Answer 4

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

using namespace std;
using data=std::pair<int,int>;
void search_pairs(std::vector<int>& A, std::vector<int>& B, const int total, std::vector<data>& output){
std::sort(A.begin(),A.end(),[](const int i,const int j)->bool{return (i<j);});
std::sort(B.begin(),B.end(),[](const int a,const int b)->bool{return (a<b);});
std::vector<int>* minV(nullptr);
std::vector<int>* 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<nb;++i){
size_t a,b(0);
int total(0);
scanf("%lu %lu %d",&a,&b,&total);
std::vector<int> A,B;
for (size_t i=0;i<a;++i){
int aux;
scanf("%d",&aux);
A.push_back(aux);
}
for (size_t i=0;i<b;++i){
int aux;
scanf("%d",&aux);
B.push_back(aux);
}
std::vector<data> 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;
}

Answer 5

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;
}