Dati due array a e b.Tutte le coppie di elementi (a1, b1) tali che a1 appartiene all’array A e b1 appartiene all’array B la cui sum a1 + b1 = k

Sto cercando la soluzione del seguente algoritmo con una minima complessità di tempo e spazio.

Dati due array a e b, trova tutte le coppie di elementi (a1, b1) tali che a1 appartiene all’array A e b1 appartiene all’array B la cui sum a1 + b1 = k (qualsiasi numero intero).

Sono stato in grado di trovare un approccio O (n log n) in cui ordineremo uno degli array dire A e per ciascuno degli elementi b nell’array B, fare una ricerca binaria sull’array A ordinato per valore (Kb).

Possiamo migliorarlo ulteriormente?

Se hai un limite sul numero massimo ansible (chiamiamolo M) allora puoi avere una soluzione in O (M + n).

Array booleano di false e contrassegna come vero tutto il valore per l’elemento di A. Quindi, per ogni elemento b di B, verificare se l’elemento numero Kb è contrassegnato come true.

Puoi migliorarlo se stai usando una mappa hash invece di un grande array. Ma non penserei che in questo tipo di domande la mappa di hash sia una specie di imbroglio.

Comunque ti darebbe O (n) per l’inserimento e poi O (n) per la query, O (n) in totale.

MODIFICARE :

Un caso in cui ciò potrebbe essere utile.

  • Hai vettori non ordinati di dimensioni 10 ^ 6, quindi ordinarli e fare la corrispondenza è in O (n log n) con n = 10 ^ 6.
  • È necessario eseguire questa operazione 10 ^ 6 volte (diversi vettori), complessità di O (n * n * log n).
  • Il valore massimo è 10 ^ 9.

L’uso della mia idea non con booleano ma intero (incrementato ad ogni esecuzione) ti dà una complessità di:

  • “O (10 ^ 9)” per creare l’array (anche la stessa complessità di spazio)
  • O (n) ad ogni corsa, quindi O (n * n) per il totale.

Stai usando più spazio ma hai aumentato la velocità di un log dei fattori (n) ~ = 20 in questo caso!

Se gli array sono ordinati, puoi farlo in tempo lineare e archiviazione costante.

  • Inizia con due puntatori, uno puntato sull’elemento più piccolo di A, l’altro che punta sull’elemento più grande di B.
  • Calcola la sum degli elementi puntati.
  • Se è minore di k, incrementa il puntatore in A in modo che punti all’elemento successivo più grande.
  • Se è maggiore di k decrementa il puntatore in B in modo che punti al successivo elemento più piccolo.
  • Se è esattamente k hai trovato una coppia. Sposta uno dei puntatori e continua a cercare la coppia successiva.

Se gli array inizialmente non sono ordinati, puoi prima ordinarli e poi usare l’algoritmo di cui sopra. Esistono diversi approcci per l’ordinamento che è ansible utilizzare, a seconda del tipo di dati che ci si aspetta:

  • Un ordinamento di confronto, ad esempio Mergesort o Timsort .
  • Tipo di conteggio .
  • Radix sort .

Un ordinamento di confronto richiederà tempo O (n log n) in media. Gli ultimi due sono più veloci di O (n log (n)) ma possono essere poco pratici se l’intervallo di valori possibili negli array di input è molto ampio.

Creerei una tabella hash contenente gli elementi di una matrice, quindi eseguo l’iterazione con l’altra matrice cercando k - a(n) , generando un elemento di output se la ricerca è riuscita. Questo userà O (n) spazio e tempo.

In C #, potrebbe assomigliare a questo:

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

Ho usato C ++ e sembrava darmi il risultato desiderato. Spero che questo sia quello che stavi cercando.

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