Dato un array, scopri il prossimo elemento più piccolo per ogni elemento

Dato un array, trova il prossimo elemento più piccolo nella matrice per ciascun elemento senza modificare l’ordine originale degli elementi.

Ad esempio, supponiamo che l’array specificato sia 4,2,1,5,3.

La matrice risultante sarebbe 2,1, -1,3, -1.

Mi è stata fatta questa domanda in un’intervista, ma non ho potuto pensare ad una soluzione migliore della banale soluzione O (n ^ 2). Qualsiasi approccio che potrei pensare, ovvero creare un albero di ricerca binario o ordinare l’array, distorce l’ordine originale degli elementi e quindi porta a un risultato errato.

Qualsiasi aiuto sarebbe molto apprezzato.

O (N) Algoritmo

  1. Inizializza l’array di output su tutti i -1.
  2. Crea una pila vuota di indici di oggetti che abbiamo visitato nell’array di input ma non conoscono ancora la risposta nell’array di output.
  3. Iterare su ciascun elemento nell’array di input:
    1. È più piccolo dell’elemento indicizzato dalla cima dello stack?
      1. Sì. È il primo di questi elementi ad esserlo. Compila l’elemento corrispondente nel nostro array di output, rimuovi l’elemento dallo stack e riprova finché lo stack non è vuoto o la risposta è no.
      2. No. Continua a 3.2.
    2. Aggiungi questo indice allo stack. Continua iterazione da 3.

Implementazione Python

 def find_next_smaller_elements(xs): ys=[-1 for x in xs] stack=[] for i,x in enumerate(xs): while len(stack)>0 and x>> find_next_smaller_elements([4,2,1,5,3]) [2, 1, -1, 3, -1] >>> find_next_smaller_elements([1,2,3,4,5]) [-1, -1, -1, -1, -1] >>> find_next_smaller_elements([5,4,3,2,1]) [4, 3, 2, 1, -1] >>> find_next_smaller_elements([1,3,5,4,2]) [-1, 2, 4, 2, -1] >>> find_next_smaller_elements([6,4,2]) [4, 2, -1] 

Spiegazione

Come funziona

Questo funziona perché ogni volta che aggiungiamo un object allo stack, sappiamo che il suo valore è maggiore o uguale a ogni elemento nello stack già. Quando visitiamo un elemento dell’array, sappiamo che se è inferiore a qualsiasi elemento nello stack, deve essere inferiore all’ultimo elemento nello stack, perché l’ultimo elemento deve essere il più grande. Quindi non abbiamo bisogno di fare alcun tipo di ricerca in pila, possiamo solo considerare l’ultimo elemento.

Nota: è ansible saltare il passaggio di inizializzazione fino a quando si aggiunge un passaggio finale per svuotare lo stack e utilizzare ciascun indice rimanente per impostare l’elemento di matrice di output corrispondente su -1. In Python è più semplice inizializzarlo a -1 quando lo si crea.

Complessità del tempo

Questo è O (N). Il ciclo principale visita chiaramente ogni indice una volta. Ogni indice viene aggiunto allo stack esattamente una volta e rimosso al massimo una volta.

Risolvendo come domanda di intervista

Questo tipo di domanda può essere piuttosto intimidatorio in un’intervista, ma vorrei sottolineare che (si spera) un intervistatore non si aspetti che la soluzione scaturisca dalla tua mente pienamente formata. Parlali attraverso il tuo processo mentale. Il mio è andato in questo modo:

  • C’è qualche relazione tra le posizioni dei numeri e il loro prossimo numero più piccolo nella matrice? Sapere che alcuni di essi vincolano ciò che potrebbero essere gli altri?
  • Se fossi di fronte a una lavagna probabilmente disegnerei la matrice di esempio e tracciare linee tra gli elementi. Potrei anche disegnarli come un grafico a barre 2D: l’asse orizzontale è la posizione nella matrice di input e l’asse verticale è il valore.
  • Avevo l’impressione che questo mostrasse uno schema, ma non c’era carta a portata di mano. Penso che il diagramma lo renderebbe ovvio. Pensandoci attentamente, ho potuto vedere che le linee non si sovrapponevano arbitrariamente, ma si annidavano solo.
  • Intorno a questo punto, mi è venuto in mente che questo è incredibilmente simile all’algoritmo che Python usa internamente per trasformare il rientro in token virtuali INDENT e DEDENT, che avevo letto prima. Vedi “Come fa il compilatore ad analizzare il rientro?” in questa pagina: http://www.secnetix.de/olli/Python/block_indentation.hawk Tuttavia, non è stato fino a quando non ho elaborato un algoritmo che ho seguito questo pensiero e determinato che era in effetti lo stesso quindi non penso che abbia aiutato troppo. Tuttavia, se riesci a vedere una somiglianza con qualche altro problema, sai, è probabilmente una buona idea menzionarlo e dire come è simile e come è diverso.
  • Da qui la forma generale dell’algoritmo stack-based divenne evidente, ma dovevo ancora pensarci un po ‘di più per essere sicuro che avrebbe funzionato bene per quegli elementi che non avevano un elemento successivo più piccolo.

Anche se non ti viene in mente un algoritmo funzionante, prova a far capire al tuo intervistatore cosa stai pensando. Spesso è il processo di pensiero più della risposta a cui sono interessati. Per un problema difficile, non riuscire a trovare la soluzione migliore ma mostrare la comprensione del problema può essere meglio che conoscere una risposta standard ma non essere in grado di dargli molto analisi.

Iniziare a creare un BST, partendo dall’estremità dell’array. Per ogni valore, la risposta “v” sarebbe l’ultimo nodo “Destra” che avresti fatto per inserire “v”, di cui puoi facilmente tenere traccia in una versione ricorsiva o iterativa.

AGGIORNARE:

Seguendo le tue esigenze, puoi affrontare questo in modo lineare:

Se ogni elemento successivo è più piccolo dell’elemento corrente (ad es. 6 5 4 3 2 1) è ansible elaborarlo in modo lineare senza richiedere alcuna memoria aggiuntiva. Caso interessante si presenta quando si inizia a ottenere elementi confusi (ad esempio 4 2 1 5 3), nel qual caso è necessario ricordare il loro ordine fino a quando non si ottengono i loro ‘controparti più piccole’. Un semplice approccio basato sullo stack è simile a questo:

Spingere il primo elemento (a [0]) in una pila.

Per ogni elemento successivo a [i], sbirci nello stack e se value (peek ()) è maggiore di quello in mano a [i], hai il tuo prossimo numero più piccolo per quell’elemento stack (peek ()) { e continua a spuntare gli elementi fino a quando sbircia ()> a [i]}. Esponili e stampa / memorizza il valore corrispondente. altrimenti, semplicemente respingi il tuo a [i] nello stack.

Nella pila finale conterrà quegli elementi che non hanno mai avuto un valore inferiore a loro (alla loro destra). Puoi inserire -1 per loro nel tuo outpput.

ad es. A = [4, 2, 1, 5, 3];

 stack: 4 a[i] = 2, Pop 4, Push 2 (you got result for 4) stack: 2 a[i] = 1, Pop 2, Push 1 (you got result for 2) stack: 1 a[i] = 5 stack: 1 5 a[i] = 3, Pop 5, Push 3 (you got result for 5) stack: 1 3 1,3 don't have any counterparts for them. so store -1 for them. 

Supponendo che tu intendessi il primo elemento successivo che è inferiore all’elemento corrente, qui ci sono 2 soluzioni –

  1. Usa la segmentazione sqrt(N) . Dividi l’array in segmenti sqrt(N) con la lunghezza di ogni segmento pari a sqrt(N) . Per ogni segmento calcola il suo ‘elemento minimo usando un ciclo. In questo modo, hai pre-calcolato l’elemento minimo di ciascun segmento in O(N) . Ora, per ogni elemento, l’elemento inferiore successivo può essere nello stesso segmento di quello o in uno qualsiasi dei segmenti successivi. Quindi, prima controlla tutti gli elementi successivi nel segmento corrente. Se tutti sono più grandi, passa in rassegna tutti i segmenti successivi per scoprire quale ha un elemento più basso dell’elemento corrente. Se non si riusciva a trovarne, il risultato sarebbe -1 . Altrimenti, controlla ogni elemento di quel segmento per scoprire quale è il primo elemento più in basso dell’elemento corrente. Complessivamente, la complessità dell’algoritmo è O(N*sqrt(N)) o O(N^1.5) .

È ansible ottenere O(NlgN) utilizzando un albero di segmenti con un approccio simile.

  1. Ordina prima l’array in ordine crescente (mantenendo la posizione originale degli elementi come dati satellitari). Ora, supponendo che ogni elemento dell’array sia distinto, per ogni elemento, dovremo trovare la posizione originale più bassa sul lato sinistro di quell’elemento. È un classico problema RMQ (Range Min Query) e può essere risolto in molti modi, incluso un O(N) . Poiché è necessario prima ordinare, la complessità complessiva è O(NlogN) . Puoi imparare di più su RMQ in un tutorial su TopCoder .

Per alcuni motivi, trovo più semplice ragionare su “precedente elemento più piccolo”, ovvero “tutti gli elementi più piccoli” . Così applicato all’indietro dà il “prossimo più piccolo”.

Per la cronaca, un’implementazione Python in O (n) time, O (1) space (cioè senza stack), che supporta i valori negativi nella matrice:

 def next_smaller(l): """ Return positions of next smaller items """ res = [None] * len(l) for i in range(len(l)-2,-1,-1): j=i+1 while j is not None and (l[j] > l[i]): j = res[j] res[i] = j return res def next_smaller_elements(l): """ Return next smaller items themselves """ res = next_smaller(l) return [l[i] if i is not None else None for i in res] 

Ecco il codice javascript. Questo video spiega meglio Algo

 function findNextSmallerElem(source){ let length = source.length; let outPut = [...Array(length)].map(() => -1); let stack = []; for(let i = 0 ; i < length ; i++){ let stackTopVal = stack[ stack.length - 1] && stack[ stack.length - 1].val; // If stack is empty or current elem is greater than stack top if(!stack.length || source[i] > stackTopVal ){ stack.push({ val: source[i], ind: i} ); } else { // While stacktop is greater than current elem , keep popping while( source[i] < (stack[ stack.length - 1] && stack[ stack.length - 1].val) ){ outPut[stack.pop().ind] = source[i]; } stack.push({ val: source[i], ind: i} ); } } return outPut; } 

Produzione -

 findNextSmallerElem([98,23,54,12,20,7,27]) [23, 12, 12, 7, 7, -1, -1] 

Ecco un’osservazione che penso possa essere trasformata in una soluzione O (n log n). Supponiamo di avere la risposta per gli ultimi k elementi dell’array. Di cosa avresti bisogno per capire il valore per l’elemento prima di questo? Puoi pensare agli ultimi k elementi come se fossero divisi in una serie di intervalli, ognuno dei quali parte da un elemento e continua in avanti finché non colpisce un elemento più piccolo. Questi intervalli devono essere in ordine decrescente, quindi potresti pensare di fare una ricerca binaria su di essi per trovare il primo intervallo più piccolo di quell’elemento. È quindi ansible aggiornare gli intervalli per il fattore in questo nuovo elemento.

Ora, il modo migliore per rappresentarlo? Il modo migliore che ho pensato è di usare un albero di splay le cui chiavi sono gli elementi che definiscono questi intervalli e i cui valori sono l’indice a cui iniziano. È quindi ansible in tempo O (log n) ammortizzato eseguire una ricerca predecessore per trovare il predecessore dell’elemento corrente. Questo trova il primo valore più piccolo rispetto alla corrente. Quindi, in tempo O (log n) ammortizzato, inserire l’elemento corrente nell’albero. Questo rappresenta la definizione di un nuovo intervallo da quell’elemento in avanti. Per scartare tutti gli intervalli che sostituisce, si taglia quindi il figlio destro del nuovo nodo, che poiché si tratta di un albero di diffusione si trova alla radice, dall’albero.

Nel complesso, questo fa O (n) iterazioni di un processo O (log n) per il totale O (n lg n).

Ecco un algoritmo O (n) che utilizza DP (in realtà O (2n)):

 int n = array.length(); 

L’array min [] registra il numero minimo trovato dall’indice i fino alla fine dell’array.

 int[] min = new int[n]; min[n-1] = array[n-1]; for(int i=n-2; i>=0; i--) min[i] = Math.min(min[i+1],array[i]); 

Cerca e confronta attraverso la matrice originale e min [].

 int[] result = new int[n]; result[n-1] = -1; for(int i=0; i 

Ecco la nuova soluzione per trovare "il prossimo elemento più piccolo":

 int n = array.length(); int[] answer = new int[n]; answer[n-1] = -1; for(int i=0; i 
  All that is actually not required i think case 1: a,b answer : -a+b case 2: a,b,c answer : a-2b+c case 3: a,b,c,d answer : -a+3b-3c+d case 4 :a,b,c,d,e answer : a-4b+6c-4d+e . . . recognize the pattern in it? it is the pascal's triangle! 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 so it can be calculated using Nth row of pascal's triangle! with alternate + ans - for odd even levels! it is O(1) 

Puoi risolverlo in O (n) runtime con O (n) complessità spaziale. Inizia con una pila e continua a spingere gli elementi finché non trovi arr [i] tale che arr [i]

Snippet di codice:

 vector findNext(vector values) { stack st; vector nextSmall(values.size(), -1); st.push(0); for (int i = 1; i < values.size(); i++) { while (!st.empty() && values[i] < values[st.top()]) { // change values[i] < values[st.top()] to values[i] > values[st.top()] to find the next greater element. nextSmall[st.top()] = i; st.pop(); } st.push(i); } return nextSmall; } 

Soluzione con complessità di spazio O (1) e complessità di tempo O (n).

 void replace_next_smallest(int a[], int n) { int ns = a[n - 1]; for (int i = n - 1; i >= 0; i--) { if (i == n - 1) { a[i] = -1; } else if (a[i] > ns) { int t = ns; ns = a[i]; a[i] = t; } else if (a[i] == ns) { a[i] = a[i + 1]; } else { ns = a[i]; a[i] = -1; } } }