Finding più vicino numero in una gamma

Question

ho pensato un problema che è la seguente:

Abbiamo un array A di interi di dimensione n, e noi abbiamo prova cause T e in tutti i casi di test ci viene dato un certo numero m e un intervallo [s, e] cioè ci viene dato se ed e dobbiamo trovare il numero più vicino di m nell'intervallo di quell'array (A [s] -A [e]).

È possibile assumere array indicizzati da 1 a n.

Ad esempio:

A = {5, 12, 9, 18, 19} 
    m = 13 
    s = 4 and e = 5 

Quindi la risposta dovrebbe essere 18.

Vincoli:

n<=10^5 
t<=n 

Tutto quello che posso pensare è una (n) soluzione per ogni caso di test O, e penso che esista una soluzione migliore.

Answer 1

Questo è uno schizzo preliminare: Crea un segment tree dai dati. In ogni nodo, oltre ai soliti dati come gli indici sinistro e destro, si memorizzano anche i numeri trovati nel sotto-albero radicato in quel nodo, memorizzati nell'ordine ordinato. È possibile ottenere ciò quando si costruisce l'albero del segmento in ordine ascendente. Nel nodo appena sopra la foglia, si memorizzano i due valori foglia nell'ordine ordinato. In un nodo intermedio, si mantengono i numeri nel figlio sinistro e nel figlio destro, che è possibile unire insieme utilizzando la fusione standard. Ci sono nodi O (n) nell'albero e il mantenimento di questi dati dovrebbe richiedere O (nlog (n)).

Una volta ottenuto questo albero, per ogni query, percorrere il percorso fino a raggiungere il nodo o i nodi appropriati nell'intervallo specificato ([s, e]). Come mostra il tutorial, uno o più nodi diversi si combinano per formare l'intervallo specificato. Poiché la profondità dell'albero è O (log (n)), è il tempo per query per raggiungere questi nodi. Ogni query dovrebbe essere O (log (n)). Per tutti i nodi che si trovano completamente all'interno dell'intervallo, trovare il numero più vicino utilizzando la ricerca binaria nell'array ordinato memorizzato in tali nodi. Di nuovo, O (log (n)). Trova il più vicino tra tutti questi, e questa è la risposta. Pertanto, è possibile rispondere a ciascuna query nel tempo O (log (n)).

Il tutorial I link contiene altre strutture dati, come la tabella sparse, che sono più facili da implementare e dovrebbero fornire O (sqrt (n)) per query. Ma non ho pensato molto a questo.

Answer 2

Sono abbastanza sicuro che non esiste una soluzione più veloce. Una leggera variazione del tuo problema è:

Non c'è una matrice A, ma ogni caso di test contiene una matrice non ordinata di numeri da cercare. (La sezione dell'array di A da s a e).

In tal caso, non esiste chiaramente un modo migliore di una ricerca lineare per ogni caso di test.

Ora, in che modo il problema originale è più specifico della variante sopra riportata? L'unica informazione aggiunta è che tutte le fette provengono dallo stesso array. Non penso che questo ulteriore vincolo possa essere usato per un aumento di velocità algoritmico.

MODIFICA: Sono in posizione corretta. La struttura dati dell'albero del segmento dovrebbe funzionare.

Answer 3

ordina l'array e effettua la ricerca binaria. complessità: o (nlogn + logn * t)