Algoritmo di ordinamento - trova la barra della carta che vede la barra diversa

Question

Ho difficoltà a provare a trovare un algoritmo con efficienza O (n) runtine.

Fornito con una matrice di dimensione n, la matrice contiene numeri interi, ad esempio. Devo sapere quale cella dell'array (si può immaginare come barra grafica) sta cercando su quale cella.

Formalmente: lookingAtIndex(i) = max { -1} U {j | arr[j] > arr[i], j<i}, dove -1 corrisponde all'asse y.

Modifica: qual è la prima barra che è superiore alla barra corrente dove im a. Se non ce n'è uno, il suo asse Y Esempio, fornito con array: 7,3,5,2,1,9 ..

Quindi 7 sta guardando sull'asse y, 3 sta guardando 7, 5 è guardando 7, 2 su 5, 1 su 2 e 9 su asse y.

Sono un po 'perso, tutto ciò che faccio rimango in O (nLogn). Non è un algoritmo di ordinamento completo, quindi è possibile farlo con O (n). Stampa i risultati è possibile mentre è in esecuzione, non è necessario memorizzare le informazioni fino alla fine.

Answer 1

Si può fare con una pila semplice.

Compare each element a[i] with the top of the stack T 
while (T <= a[i]) 
    pop T 
if the stack is empty 
    a[i] is looking at the y-axis 
else 
    a[i] is looking at T 
push a[i] onto the stack 

Ad esempio, utilizzando la matrice [7,3,5,2,1,9]

a[0]=7 T=empty  7 is looking at y-axis 
a[1]=3 T=7   3 is looking at 7 
a[2]=5 T=3 pop 3 
     T=7   5 is looking at 7 
a[3]=2 T=5   2 is looking at 5 
a[4]=1 T=2   1 is looking at 2 
a[5]=9 T=1 pop 1 
     T=2 pop 2 
     T=5 pop 5 
     T=7 pop 7 
     T=empty  9 is looking at y-axis 

nota che ogni numero viene inserito nello stack, e ogni numero può essere spuntato solo una volta dalla pila, quindi il numero di operazioni di stack è al massimo 2N e l'intero algoritmo è O (n).

Answer 2

Mi dirigo verso una soluzione lineare, con un grande fattore avanti. Quindi penso che potrebbe non essere la soluzione migliore.

Ecco la cosa. Chiamiamo la matrice di input degli interi I, di lunghezza n. Lascia che sia M il numero più grande in I, trovato in O(n). Presumo innanzitutto che il valore minimo in I sia 0; in caso contrario, sottrarre il valore minimo non cambia la soluzione e M è nel caso generale max(I)-min(I).

Creare un array T di lunghezza m, con tutti gli elementi impostati su -1. Questa matrice è la memorizzazione degli indici della barra "guardata" per ogni numero intero possibile in I; l'inizializzazione è -1, indice di una barra virtuale più a sinistra.

Creare anche l'array S come matrice di output degli indici delle barre "guardate".

Ora, per ciascun elemento e in I con indice i nell'array, sembra al bar il cui indice è appunto T[e]. Quindi S[i] = T[e]. Quindi imposta tutti gli elementi T[0..e] con il valore i.

Alla fine del ciclo, S viene riempito con gli indici delle barre "guardate"; è facile recuperare il valore di queste barre.

Come si può vedere, la complessità complessiva è O(M*n), quindi la complessità è lineare con la lunghezza di I. Potrebbe non essere molto efficiente a causa del fattore M come ho detto prima (qualsiasi miglioramento è ben accetto).

EDIT

Preferisco la soluzione di user3386109, il mio è imbarazzante in confronto.

Answer 3

Diciamo che abbiamo un array che termina con: ... A - B,

e lookingAtIndex (A) = X, e cerchiamo di trovare il risultato per la B: se A> B, allora si tratta di A, altrimenti tutti gli indici tra A e lookingAtIndex (A) non possono essere una buona risposta dato che sono inferiori ad A, se lookingAtIndex (A)> B allora è la risposta else guarda aAtIndex (lookingAtIndex (A)) ecc ..

Ma avrete bisogno di un modo per memorizzare le barre di ogni indice, penso che l'idea della pila data dall'utente3386109 sia un'implementazione molto buona, e avrete solo bisogno di memorizzare i valori necessari