Unire due sequenze ordinate
Scorrere entrambe le liste con un puntatore ciascuna
Unire due sequenze ordinate è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Il passaggio di fusione
Date due liste ordinate, occorre combinarle in un'unica lista ordinata. Questa fusione è il cuore di merge sort e ricorre in moltissimi contesti. 🔗
Due input, un puntatore ciascuno
Si assegna a ogni lista il proprio puntatore, entrambi inizialmente all'indice 0. Li si fa avanzare insieme, senza mai tornare indietro.
i = 0
j = 0Scegliere sempre il minore
A ogni passaggio si confrontano i due primi elementi. Si aggiunge il minore al risultato, perché deve essere il successivo nell'ordine crescente.
Far avanzare il vincitore
Dopo aver prelevato un valore, si fa avanzare solo il puntatore della lista da cui proveniva. Nell'altra lista rimane in attesa il suo elemento più piccolo.
if a[i] <= b[j]:
out.append(a[i])
i += 1
else:
out.append(b[j])
j += 1Il ciclo principale
Si continua a fondere while entrambe le liste contengono ancora elementi. Quando una delle due si esaurisce, il confronto non è più necessario.
while i < len(a) and j < len(b):
# compare and append
passSvuotare ciò che rimane
Quando una lista si svuota, l'altra è già ordinata, quindi è sufficiente append direttamente al risultato la coda rimanente.
out.extend(a[i:])
out.extend(b[j:])Perché le code sono gratuite
La coda rimanente è già ordinata, quindi non servono altri confronti. Una delle due chiamate a extend aggiunge semplicemente zero elementi.
Tempo lineare complessivo
Ogni elemento viene esaminato una volta, quindi la fusione di due liste di dimensioni n e m richiede O(n + m). È il tempo migliore possibile.
Mantenere la stabilità
Usare <= quando i valori sono uguali mantiene gli elementi equivalenti nell'ordine originale. Questa stabilità è importante quando si portano con sé dati aggiuntivi.
Fondere anche al contrario
Per fondere in un buffer senza spazio libero aggiuntivo, si procede invece dal fondo, collocando per ultimo l'elemento più grande. È la stessa idea, applicata al contrario.
Dalla fusione all'ordinamento
Dividere, ordinare le metà e poi fonderle: questa ricorsione è merge sort. La fusione con due puntatori appena appresa ne è il motore principale.
Verifica rapida
Si stanno fondendo due liste ordinate usando un puntatore per ciascuna.
Riepilogo
Si attraversano due liste ordinate con un puntatore ciascuna, scegliendo sempre il primo elemento più piccolo, quindi si aggiunge la coda rimanente. Il procedimento richiede O(n + m) ed è alla base di merge sort. 🚀
Domande Frequenti
La lezione «Unire due sequenze ordinate» è gratuita?
Sì — il testo completo di «Unire due sequenze ordinate» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Unire due sequenze ordinate»?
Scorrere entrambe le liste con un puntatore ciascuna Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.
Quanto tempo richiede la lezione «Unire due sequenze ordinate»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Due puntatori su un array ordinato
- Trovare una coppia con una somma data
- Rimuovere i duplicati sul posto
- Unire due sequenze ordinate