O (n) Algoritmo per scoprire se 2 array hanno 2 elementi che si sommano a un numero

Question

Sto studiando per un esame e ho trovato questa domanda che sembra un po 'complicata.

Sia A [1 ... n] e B [1 ... n] siano 2 matrici di numeri interi tali che ciascun elemento di A o B sia compreso tra 0 e m dove m = O (n). (Io parto dal presupposto che significa m < n?)

Abbiamo bisogno di progettare un O (n) algoritmo che trova due elementi A [i] e B [j] tale che A [i] + B [j ] = un dato numero k. Se non esistono, lanciamo un messaggio di errore.

Ora l'ordinamento sarebbe fuori questione, poiché i migliori algoritmi di ordinamento sono O (n lg n).

Forse utilizzare una tabella hash .. O semplicemente creare un array più piccolo X di lunghezza m tale che ogni indice conta le occorrenze di un numero in A .. quindi passiamo attraverso B .. calcola diff = k - B [j ] .. e controllare X [diff] .. se è maggiore di zero, allora sì, esiste, allora potremmo passare attraverso un nuovo per trovare il suo indice ..

Cosa ne pensate voi ragazzi

Answer 1

m = O(n) significa che m è limitato da un multiplo costante di n, non necessariamente più piccolo di esso.

Quello che puoi fare è questo. Ottieni un array con la dimensione k+1 (quindi la memoria O(m) che è anche O(n)). Chiama questo array C. Inizializza tutti i valori come non marcati, diciamo -1. Questo è O(m) che è anche O(n).

Ora sai che k <= 2m perché A[i] e B[i] sono entrambi <= m.Quindi passa attraverso l'array A, contrassegna in C tutto k-A[i], quindi C[k-A[i]] = i (ovvero se k-A[i] >= 0presupponendo che gli indici inizino da 0). Questo è O(n). Quindi passare attraverso l'array B e per ogniverificare se C[B[j]] è già stato contrassegnato. In tal caso, quindi C[B[j]] contrassegna un determinato indice in A dove B[j]+A[C[B[j]]] = k. Superando B e controllando il segno è anche O(n). Se non trovi una corrispondenza, non esiste una tale coppia.

L'algoritmo complessivo è O(n).

Ecco un esempio:

n = 5 
m = 15 
A = [1 7 4 2 10] 
B = [8 14 3 13 11] 
k = 20 

Dopo andando oltre A, si ottiene:

C: [-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 4 -1 -1 1 -1 -1 2 -1 3 0 -1] 

(spaziatura è per una migliore visualizzazione) Poi si controlla contro B:

B[0] -> C[8] -> -1 mismatch 
B[1] -> C[14] -> -1 mismatch 
B[2] -> C[3] -> -1 mismatch 
B[3] -> C[13] -> 1 match -> B[3] + A[1] = 20 

B[3] era 13 e A[1] era 7.

Answer 2

Useremo una tabella hash che contiene la differenza tra ogni elemento nel primo array e la somma. Fondamentalmente basta scorrere il primo array, calcolare la differenza tra la somma e ogni elemento dell'array e memorizzarlo nella tabella hash. Quindi scorrere il secondo array, controllando se ciascun numero appare nella tabella hash

Answer 3

È possibile ordinare in O (n) utilizzando il metodo della tabella hash che hai descritto (si potrebbe semplicemente memorizzare un valore booleano invece di un int poiché è sufficiente bisogno di sapere se esiste). In generale, gli ordinamenti di confronto non sono migliori di O (n lg n) ma se si conoscono determinati vincoli si può fare meglio (o se si possono usare ordinamenti di non confronto come radix sort (che penso si possa usare anche qui)) . Fondamentalmente:

1. Inizializza una matrice, A ', di dimensione n e imposta tutti i valori su falso.
2. Per ciascun elemento in A, impostare l'indice corrispondente in A 'su vero.
3. Per ogni elemento in A ', se il valore è true, aggiungere l'indice a un altro array A' '.
4. Un '' è ora un A ordinato, con i duplicati rimossi.
5. Ripetere l'operazione per B.

Il problema dovrebbe essere abbastanza banale, ora che avete A e B allineati.