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