Il più grande elemento presente sul lato destro di ogni elemento di un array

Question

Mi è stata assegnata una matrice (di n elementi) e devo trovare l'elemento più piccolo sul lato destro di ciascun elemento che è maggiore di se stesso (elemento corrente).

For example : 
    Array =  {8,20,9,6,15,31} 
Output Array = {9,31,15,15,31,-1} 

È possibile risolvere questo in O(n).? Ho pensato di attraversare l'array dal lato destro (a partire da n-2) e di costruire un albero di ricerca binaria di bilancio per gli elementi rimanenti, poiché la ricerca in esso per un elemento che è immediatamente maggiore dell'elemento corrente sarebbe O (logn).

Quindi complessità temporale sarebbe venuto fuori per essere O (n * (log (n)).

v'è un approccio migliore a questo problema?

Answer 1

Il problema si presenti è impossibile da risolvere in O(n) tempo, dato che è possibile ridurre l'ordinamento di esso e quindi realizzare la cernita in O(n) tempo. Say esiste un algoritmo che risolve il problema in O(n). sia un elemento un.

L'algoritmo può anche essere utilizzato per trovare l'elemento più piccolo al sinistra di e grandi di un (dal invertendo la matrice prima di eseguire l'algoritmo). Può anche essere usato per trovare l'elemento più grande al destra (o sinistra) di e minore di un (dai negando gli elementi prima di eseguire l'algoritmo).

Così, dopo aver eseguito l'algoritmo di quattro volte (in tempo lineare), si sa quali elementi devono essere alla destra e alla sinistra del di ogni elemento. Al fine di costruire l'array ordinato in tempo lineare, è necessario mantenere gli indici degli elementi anziché i valori. Per prima cosa trovi l'elemento più piccolo seguendo i tuoi "puntatori più grandi" in tempo lineare, quindi fai un altro passaggio nell'altra direzione per costruire effettivamente l'array.

Answer 2

Questo non può essere eseguito in O(n), poiché è possibile ridurre Element Distinctness Problem (che è noto per essere sovrascrivibile in Omega (nlogn) quando si effettua il confronto) ad esso.

In primo luogo, facciamo un po 'di espansione al problema, che non influenza la sua durezza:

mi è stato dato un array (di n elementi) e devo trovare l'elemento più piccolo sul lato destro di ogni elemento che è maggiore/uguale a di se stesso (elemento corrente).

L'aggiunta è ci permettono l'elemento sia uguale ad esso (a destra), e non solo strettamente maggiore di 1 .

Ora, dato un esempio di elemento di distinzione arr, eseguire l'algoritmo per questo problema, e guardate se c'è qualche elemento i tale che arr[i] == res[i], se non c'è non rispondere "tutti distinti", altrimenti: "Non tutti distinti ".

Tuttavia, poiché la distinzione degli elementi è basata su confronto Omega(nlogn), rende questo problema altrettanto utile.

---

(1) Una possibile giustificazione perché l'aggiunta di parità non sfrutta al problema più difficile è - elementi assumendo sono numeri interi, possiamo solo aggiungere i/(n+1) a ciascun elemento della matrice, ora per ogni due elementi se arr[i] < arr[j] , anche arr[i] + i/(n+1) < arr[j] + j/(n+1), ma se arr[i] = arr[j], quindi se i<jarr[i] + i/(n+1) < arr[j] + j/(n+1), e possiamo avere lo stesso algoritmo risolvere il problema anche per le uguaglianze.

Answer 3

Altri hanno dimostrato che è impossibile in generale risolvere in O (n).

Tuttavia, è possibile eseguire in O (m) dove m è la dimensione dell'elemento più grande.

Ciò significa che in alcuni casi (ad esempio se la matrice di input è nota per essere una permutazione degli interi da 1 a n), allora è possibile eseguire in O (n).

Il codice seguente mostra l'approccio, basato su un metodo standard per calcolare l'elemento successivo più grande. (C'è una buona spiegazione di questo metodo on geeks for geeks)

def next_greater_element(A): 
    """Return an array of indices to the next strictly greater element, -1 if none exists""" 
    i=0 
    NGE=[-1]*len(A) 
    stack=[] 
    while i<len(A)-1: 
     stack.append(i) 
     while stack and A[stack[-1]]<A[i+1]: 
      x=stack.pop() 
      NGE[x]=i+1 
     i+=1 
    return NGE 

def smallest_greater_element(A): 
    """Return an array of smallest element on right side of each element""" 
    top = max(A) + 1 
    M = [-1] * top # M will contain the index of each element sorted by rank 
    for i,a in enumerate(A): 
     M[a] = i 
    N = next_greater_element(M) # N contains an index to the next element with higher value (-1 if none) 
    return [N[a] for a in A] 


A=[8,20,9,6,15,31] 
print smallest_greater_element(A) 

L'idea è quella di trovare l'elemento successivo in ordine di grandezza con maggiore indice. Questo prossimo elemento sarà quindi il più piccolo che appare a destra.