Algoritmo per la ricerca di 2 elementi con una differenza data in una matrice

Question

Mi viene data una matrice di numeri reali, A. Ha n + 1 elementi. E 'noto che vi sono almeno 2 elementi dell'array, x ed y, tali che:

abs(x-y) <= (max(A)-min(A))/n 

ho bisogno di creare un algoritmo per trovare le 2 copie (se ci sono più, ogni coppia è buono) nel tempo O (n).

Ho provato per qualche ora e sono bloccato, qualche indizio/suggerimento?

Answer 1

woo I got it! Il trucco è nel Pigeonhole Principle.

Ok .. pensa ai numeri come punti su una linea. Quindi, min(A) e max(A) definiscono rispettivamente i punti iniziale e finale della linea. Ora dividi quella linea in n intervalli uguali di lunghezza (max(A)-min(A))/n. Dato che ci sono i punti n+1, due di questi devono rientrare in uno degli intervalli.

Si noti che non è necessario fare affidamento sulla domanda che ci dice che ci sono due punti che soddisfano il criterio. Ci sono sempre due punti che lo soddisfano.

L'algoritmo stesso: è possibile utilizzare una forma semplificata di tipo di benna qui, poiché è necessario un solo elemento per bucket (premere due e il gioco è fatto).Primo ciclo una volta attraverso l'array per ottenere min(A) e max(A) e creare un array intero buckets[n] inizializzato su un valore predefinito, ad esempio -1. Poi per un secondo passaggio:

for (int i=0; i<len; i++) { 
    int bucket_num = find_bucket(array[i]); 
    if (bucket[bucket_num] == -1) 
     bucket[bucket_num] = i; 
    else 
     // found pair at (i, bucket[bucket_num]) 
} 

Dove find_bucket(x) restituisce il risultato intero arrotondato-down x/((max(A)-min(A))/n).

Answer 2

Riassegniamo il problema: dobbiamo trovare due elementi, ad esempio abs(x-y) <= c, dove c è una costante, che possiamo trovare nel tempo O(n). (In effetti, possiamo calcolare sia max(A) e min(A) in tempo lineare e basta assegnare c=(max-min)/n).

Immaginiamo abbiamo una serie di segmenti, in modo che in primi elementi di benna 0<=x<c verranno effettuati nei secondi elementi benna c<=x<=2c immessi, ecc Per ogni elemento, possiamo determinare il suo secchio per O(1) tempo. Si noti che il numero di bucket occupati non sarà superiore al numero di elementi nella matrice.

Andiamo a ripetere l'array e posizionare ciascun elemento nel suo bucket. Se nel bucket lo inseriremo, esiste già un altro elemento, quindi abbiamo appena trovato la coppia corretta di x e !

Se abbiamo iterato l'intero array e ogni elemento è caduto nel suo stesso secchio, nessuna preoccupazione! Iterate i bucket ora (non ci sono più di n bucket, come abbiamo detto sopra) e per ogni elemento bucket x, se nel prossimo bucket elemento è tale che abs(x-y)<=c, quindi abbiamo trovato la soluzione.

Se abbiamo ripetuto tutti i bucket e non abbiamo trovato elementi corretti, non c'è soluzione. OMG, mi sono davvero perso quella roba da piccionaia (vedi the other answer).

I bucket possono essere implementati come una mappa hash, in cui ciascun bucket contiene un indice di array (l'elemento di posizionamento nel bucket sarà simile al seguente: buckets[ a[i]/c] = i). Calcoliamo c nell'orario O(n), assegna gli elementi ai bucket nel tempo O(n)*O(1) (O(1) è l'accesso alla mappa hash), attraversa i bucket nel tempo O(n). Pertanto, l'intero algoritmo è lineare.