Sort List
Ti viene fornita una lista semplicemente concatenata memorizzata in due array della stessa lunghezza. Il nodo i contiene il valore values[i] e punta al nodo next[i]; -1 indica la fine della lista e la testa è il nodo 0. I nodi non sono memorizzati nell'ordine della lista e gli array possono contenere anche nodi residui che la visita a partire dal nodo 0 non raggiunge mai. Questi nodi non fanno parte della lista, anche se i loro collegamenti puntano al suo interno.
Ordina la lista in ordine non decrescente di valore e restituisci i valori dei suoi nodi in quest'ordine.
Funzione
- nextinteger-array
- l'indice del nodo a cui è collegato ciascun nodo, oppure -1 per l'ultimo nodo
- valuesinteger-array
- il valore contenuto in ciascun nodo
- Restituisceinteger-array
- i valori dei nodi della lista, dal più piccolo al più grande
Vincoli
1 ≤ n ≤ 4000, dovenè la lunghezza dinexte divalues.-1000 ≤ values[i] ≤ 1000- Ogni
next[i]è-1oppure un indice di nodo da0an-1. - Partendo dal nodo
0, la lista raggiunge-1senza visitare due volte lo stesso nodo. - Nodi che il percorso dal nodo
0non raggiunge non fanno parte della lista. Le loro vocinextpossono puntare ovunque.
Esempi
- Input
- next = [3, -1, 4, 2, 1]values = [4, 1, 3, 2, 5]
- Output
- [1, 2, 3, 4, 5]
- Spiegazione
- Il percorso dal nodo
0visita i nodi0, 3, 2, 4, 1, quindi la lista è4, 2, 3, 5, 1. Ordinata, diventa1, 2, 3, 4, 5.
- Input
- next = [2, 0, -1, -1]values = [6, 9, -2, 5]
- Output
- [-2, 6]
- Spiegazione
- La lista è
0 → 2, che contiene6, -2. I nodi1e3non vengono mai raggiunti dalla testa, quindi i loro valori9e5vengono esclusi, anche se il nodo1è collegato al nodo0.
- Input
- next = [1, 2, 3, -1]values = [3, -1, 3, -1]
- Output
- [-1, -1, 3, 3]
- Spiegazione
- La lista è
3, -1, 3, -1. I valori uguali rimangono nella risposta tante volte quante compaiono:-1, -1, 3, 3.
Per approfondire
Riesci a ordinare ricollegando i nodi in tempo O(n log n), senza copiare i valori all'esterno?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Quali algoritmi di ordinamento devono saltare a una posizione arbitraria e quali invece procedono sempre in avanti nel loro input? Una lista concatenata è adatta al secondo tipo.
Per unire due liste ordinate in una sola non serve memoria aggiuntiva: ricolleghi i nodi, scegliendo sempre il più piccolo dei due valori in testa. Se potessi dividere la lista in due metà ordinate, basterebbe una fusione per completare il lavoro.
Trova il centro con un puntatore lento e uno veloce e taglia la lista in quel punto. Ordina ciascuna metà allo stesso modo, fermandoti a un singolo nodo, che è già ordinato. Poi unisci le due metà ordinate e restituisci la nuova testa.
Soluzione
Quicksort e heapsort si basano sull'accesso casuale, mentre una lista collegata singolarmente procede solo in avanti. Il merge sort è adatto: dividere una lista a metà e unire due liste ordinate comporta in entrambi i casi un percorso in avanti, quindi ordina i collegamenti stessi in O(n log n). Qui n è la lunghezza degli array.
Copia i valori in un array e ordinali
Intuizione
La lista è costituita da ciò che visita il percorso node = next[node] dal nodo 0 fino a -1. Raccogli quei valori in un nuovo array, ordinalo con il metodo di ordinamento integrato e restituiscilo. Non puoi ordinare direttamente values: nel secondo esempio contiene 9 e 5, che non fanno parte della lista.
Il percorso è O(n) e l'ordinamento O(n log n), con O(n) di memoria aggiuntiva. La lista stessa non viene mai toccata, ed è per questo che chi fa i colloqui chiede l'approccio successivo.
Algoritmo
- Inizia con un array vuoto e
node = 0. - Mentre
nodeè diverso da-1, aggiungivalues[node]e passa anext[node]. - Ordina l’array in ordine crescente e restituiscilo.
def sortList(next, values):
# Collect the values of the nodes on the list, then sort them.
on_list = []
node = 0
while node != -1:
on_list.append(values[node])
node = next[node]
on_list.sort()
return on_listOrdinamento per fusione sui link
Intuizione
Un puntatore lento che avanza di un collegamento e un puntatore veloce che avanza di due trovano il centro con un'unica scansione. Per fondere due liste ordinate bastano i loro nodi iniziali: prendi quello più piccolo e avanza oltre. Nessuno dei due passaggi richiede un secondo array.
Nel primo esempio, slow si ferma sul 3 e, tagliando il suo collegamento, 4, 2, 3, 5, 1 si divide in 4, 2, 3 e 5, 1. Queste vengono ordinate in 2, 3, 4 e 1, 5, e la fusione prende 1, 2, 3, 4, poi collega il 5 rimasto.
Ogni livello di suddivisione visita ogni nodo un numero costante di volte, e ci sono circa log n livelli, quindi il tempo è O(n log n). L'unica memoria aggiuntiva è lo stack di ricorsione, profondo circa 12 chiamate per 4000 nodi.
Algoritmo
- Se la lista ha un nodo (
next[head] == -1), restituiscihead. - Imposta
slow = headefast = next[head]; fai avanzareslowdi un collegamento efastdi due mentrefastenext[fast]sono diversi da-1. - Imposta
second = next[slow]e separa connext[slow] = -1. - Ordina ricorsivamente entrambe le metà. Fondile: collega il nodo iniziale più piccolo dopo
tailfinché una metà non è vuota, quindi collega il resto dell’altra. - Percorri la lista a partire dalla testa restituita e raccogli i valori.
def sortList(next, values):
def merge(a, b):
# Splice two sorted lists into one; on a tie the node from a goes first.
head = tail = -1
while a != -1 and b != -1:
if values[b] < values[a]:
node, b = b, next[b]
else:
node, a = a, next[a]
if tail == -1:
head = node
else:
next[tail] = node
tail = node
next[tail] = a if a != -1 else b # attach whatever is left
return head
def sort(head):
if next[head] == -1: # one node is already sorted
return head
# slow stops on the last node of the first half
slow, fast = head, next[head]
while fast != -1 and next[fast] != -1:
slow = next[slow]
fast = next[next[fast]]
second = next[slow]
next[slow] = -1 # cut the list in two
return merge(sort(head), sort(second))
result = []
node = sort(0)
while node != -1:
result.append(values[node])
node = next[node]
return result
Trappole e casi limite
- Ordinare l'intero array
values. Nel secondo esempio vengono introdotti9e5, che non sono nell'elenco. - Iniziare
fastsulla testa. Con due nodi,slowarriva poi al secondo nodo, il taglio lascia la seconda metà vuota e la ricorsione non riduce mai la dimensione. - Dimenticare il taglio
next[slow] = -1. La prima metà prosegue quindi nella seconda e le due chiamate ordinano liste sovrapposte. - Scartare il resto di una metà quando l'altra si esaurisce. Quei nodi scompaiono dal risultato.
- In Lua e R, gli array iniziano da 1: mantieni gli indici dei nodi a partire da 0 e leggi
next[node + 1]. La versione in R copia una volta l'array dei collegamenti, quindi usa O(n) memoria aggiuntiva.
Domande frequenti3
Qual è il modo migliore per ordinare una lista concatenata?
Ordinamento per fusione. Dividere a metà, ordinare entrambe le metà e fonderle procede sempre in avanti lungo la lista, l'unica direzione supportata da una lista concatenata semplice. Ha una complessità temporale di O(n log n) e ricollega i nodi esistenti.
Perché il merge sort è preferito al quicksort per le liste concatenate?
Quicksort può suddividere una lista ricollegando gli elementi, ma un buon pivot richiede accesso casuale e scegliere la testa come pivot fa sì che una lista ordinata abbia un costo di O(n²). Merge sort divide sempre a metà, quindi rimane O(n log n) con qualsiasi input.
Riesci a ordinare una lista concatenata in tempo O(n log n) e con memoria O(1)?
Sì, con l'ordinamento per fusione bottom-up. Unisce le sequenze adiacenti di lunghezza 1, poi 2, poi 4, finché una sequenza non copre l'intera lista. Ci sono log n passate lineari e l'unica memoria necessaria consiste in pochi indici di nodi.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def sortList(next, values):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomenti
next = [3, -1, 4, 2, 1] values = [4, 1, 3, 2, 5]
Output atteso
[1, 2, 3, 4, 5]