Trova il numero massimo di coppie di numeri che si trovano in un intervallo, tra due array

Question

Trova il numero massimo di coppie di numeri che si trovano in un intervallo, tra due array

#1 da (2 voti)
#2 da (-1 voti)

2

Diciamo che ho due array A e B

A = {1,2,3}
B = {12,11,67}
and have max sum value S = 10

Quanti numeri massimi di coppie uniche possono essere formati tra i due array la cui somma è inferiore o uguale a S.

Ad esempio, i due valori possibili qui sono [1,11] [2,12] quindi la risposta è 2. Se non ce ne sono, la risposta è 0.

La mia soluzione era di ordinare entrambi gli array e poi andare a fare

 if((Math.abs(A[i]-B[i]))<=S)
                 {
                 ans++;
             }

Sebbene funzioni per questo caso, chiaramente questo non è corretto.

java array algorithms

posta WeirdAl 21.06.2015 - 04:27

fonte

2 risposte

Leggi altre domande sui tag java array algorithms

Modificatore di accesso di costruttori di classi astratte Come evitare di legare questi due metodi insieme allo stato globale mutabile?

score 2 · Answer 1

La chiave per farlo in modo efficiente è sfruttando il fatto che se a1 < a2 , poi pair(a2) \subseteq pair(a1) , dove pair(a) = {b \in B : a + b <= S} . Esempio di codice Java:

Arrays.sort( A );
Arrays.sort( B );
int count = 0;
int j = B.length - 1;
for( int i = 0; i < A.length; ++i ) {
    while( j >= 0 ) {
        if( A[i] + B[j] <= S ) {
            break;
        }
        --j;
    }
    if( j < 0 ) {
        break;
    }
    count += (j + 1);
}

Questo codice presuppone che non vi siano duplicati in A o B . L'operazione dominante è l'ordinamento O(n log n) . Il ciclo attraversa ogni elenco una volta, quindi la complessità complessiva è O(n log n + 2n) che è in O(n log n) . Se ci sono duplicati possono essere rimossi dagli elenchi ordinati in tempo lineare.

score -1 · Answer 2

Supponi che A e B abbiano un milione di membri e hai ordinato A e B.

Quante coppie puoi formare con A [0]? Per scoprirlo, aggiungi A [0] + B [0], A [0] + B [1], A [0] + B [2] ecc. Ti fermi quando il risultato è troppo grande, e allora sai quanti. Dire A [0] + B [920178] non è troppo grande, ma A [0] + B [920179] è troppo grande, quindi è possibile formare coppie 920179 usando A [0]. Questo metodo funziona perché B è ordinato.

Quante coppie puoi formare con A [1]? Poiché A è ordinato, A [0] < = A [1]. Ciò significa che A [1] + B [920179] è troppo grande. Si ricerca verso il basso fino a trovare ad esempio che A [1] + B [920174] non è troppo grande. Questo dà un'altra 920175 coppie.

Ripeti lo stesso con A [2], A [3] fino ad A [999999]. Quindi quanto ci vuole? Esaminate un milione di valori di A. Esaminate al massimo un milione di valori di B, perché la vostra ricerca verso il basso attraverso B terminerà con B [0].

Dovrai essere un po 'attento all'estremità degli array per evitare bug nel tuo codice.