Merge Sorted Array

Q: Qual è la complessità temporale della fusione di due array ordinati?

Con due puntatori è O(m + n) , dove m e n sono le due lunghezze. A ogni passaggio viene inserito un valore e nessun valore viene esaminato due volte. Concatenare e ordinare costa invece O((m + n) log(m + n)) .

Q: Come si uniscono sul posto due array ordinati?

Quando il primo array ha spazio sufficiente in fondo per entrambi, riempilo partendo dalla fine. Confronta i valori rimanenti più grandi dei due array, scrivi quello più grande nell'ultimo spazio libero e spostati a sinistra. Scrivere partendo dalla fine non sovrascrive mai un valore del primo array che non è ancora stato posizionato, quindi non serve un secondo array.

Q: Unire due array ordinati è la stessa cosa della fase di unione del merge sort?

Sì. Merge sort divide un array a metà, ordina ciascuna metà e poi unisce le due metà ordinate usando esattamente questo ciclo con due puntatori. Scegliere il valore a sinistra in caso di parità mantiene i valori uguali nel loro ordine originale, ed è questo che rende stabile merge sort.

Q: Perché non concatenare gli array e chiamare sort?

Fornisce la risposta corretta e, nella pratica, spesso è veloce. Ma ignora il fatto che gli input sono già ordinati e comporta un fattore log aggiuntivo. In un colloquio, la fusione con due puntatori è la risposta attesa, perché dimostra che sai sfruttare l’ordine che ti è stato fornito.

FacileDue puntatori Ordinamento

+10

Ti vengono forniti due array di numeri interi, nums1 e nums2. Ognuno è già ordinato in ordine non decrescente. Restituisci un unico array che contenga tutti i valori di entrambi, anch’esso in ordine non decrescente. Un valore che compare in entrambi gli array compare nel risultato tante volte quante compare in totale.

Funzione

merge(nums1: integer-array, nums2: integer-array) → integer-array

nums1integer-array: il primo array ordinato
nums2integer-array: il secondo array ordinato
Restituisceinteger-array: tutti i valori di entrambi gli array in un unico array ordinato, di lunghezza nums1.length + nums2.length

Vincoli

1 ≤ nums1.length, nums2.length ≤ 2000
-10⁵ ≤ nums1[i], nums2[j] ≤ 10⁵
nums1 e nums2 sono ciascuno ordinati in ordine non decrescente.

Esempi

Input: nums1 = [1, 4, 9]nums2 = [2, 3, 10]
Output: [1, 2, 3, 4, 9, 10]
Spiegazione: Leggi i due elementi in testa e conserva il più piccolo: 1, poi 2 e 3 da nums2, poi 4 e 9 da nums1, e infine 10. Il risultato contiene tutti e sei i valori.

Input: nums1 = [-5, 0, 0, 8]nums2 = [0, 6]
Output: [-5, 0, 0, 0, 6, 8]
Spiegazione: Lo 0 compare due volte in nums1 e una volta in nums2, quindi il risultato contiene tre 0. Il -5 è più piccolo di tutti gli elementi in nums2 e viene per primo.

+13 test nascosti all’invio

Per approfondire

Riesci a fondere k array ordinati, contenenti in totale N valori, in tempo O(N log k)?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Unire gli array e ordinarli dà la risposta corretta, ma ignora il fatto che entrambe le metà sono già ordinate. Il valore più piccolo rimasto in assoluto si trova sempre all’inizio di uno dei due array. Mantieni un indice per array, scegli a ogni passaggio il valore più piccolo tra i due in testa e una sola passata costruisce il risultato. Questo è il passaggio di fusione del merge sort.

Concatenare e ordinare

Intuizione

Inserisci ogni valore di nums1 e ogni valore di nums2 in un unico array, quindi ordinalo. Il risultato contiene i valori corretti, ciascuno tante volte quante è apparso, nell’ordine corretto.

Per [1, 4, 9] e [2, 3, 10], l’array unito è [1, 4, 9, 2, 3, 10] e l’ordinamento produce [1, 2, 3, 4, 9, 10].

Con m valori in nums1 e n in nums2, un ordinamento generico ha un costo di O((m + n) log(m + n)). Funziona ed è abbastanza veloce per questi limiti, ma non sfrutta l’ordine già presente nei dati forniti. Il prossimo approccio lo fa e riduce il fattore logaritmico.

Algoritmo

Crea un array con i valori di nums1 seguiti da quelli di nums2.
Ordinalo in ordine numerico crescente.
Restituiscilo.

def merge(nums1, nums2):
    return sorted(nums1 + nums2)

Due puntatori, uno per array

Intuizione

Mantieni un indice i in nums1 e un indice j in nums2, entrambi inizializzati a 0. Tutto ciò che precede i e j è già nel risultato. Il valore più piccolo non ancora usato è nums1[i] oppure nums2[j], perché ogni array è ordinato e i suoi valori rimanenti possono solo essere maggiori. Aggiungi quello più piccolo e sposta quell’indice.

Con [1, 4, 9] e [2, 3, 10]: 1 batte 2, poi 2 batte 4, 3 batte 4, 4 batte 10, 9 batte 10. A questo punto nums1 è esaurito, quindi il resto di nums2, cioè [10], viene copiato così com’è. Il risultato è [1, 2, 3, 4, 9, 10].

Ogni passaggio scrive un valore, quindi il ciclo viene eseguito m + n volte: tempo O(m + n). L’array del risultato è l’unica memoria aggiuntiva.

Algoritmo

Imposta i e j a 0 e crea un risultato vuoto.
Finché entrambi gli array contengono ancora valori, confronta nums1[i] con nums2[j].
Aggiungi quello più piccolo e fai avanzare il suo indice. In caso di parità, scegli nums1[i].
Quando un array si esaurisce, aggiungi ciò che resta dell'altro.
Restituisci il risultato.

def merge(nums1, nums2):
    result = []
    i = j = 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] <= nums2[j]:
            result.append(nums1[i])
            i += 1
        else:
            result.append(nums2[j])
            j += 1
    # one array is used up; the rest of the other is already sorted
    result.extend(nums1[i:])
    result.extend(nums2[j:])
    return result

Trappole e casi limite

La maggior parte dei bug si presenta quando uno degli array termina o nel modo in cui vengono confrontati i valori.

Interrompere il ciclo appena uno degli array è esaurito e dimenticare il resto dell’altro. Con [1, 2, 3] e [4, 5, 6], il ciclo termina dopo 1, 2 e 3, e 4, 5, 6 devono ancora essere copiati.
Leggere nums1[i] dopo che i ha raggiunto la fine. Controlla entrambi gli indici prima di confrontarli.
Eliminare i duplicati. [0, 0] e [0] si uniscono in [0, 0, 0], non [0].
In JavaScript e TypeScript, sort() senza comparatore ordina i numeri come testo, quindi [-5, 10, 9] viene ordinato come [-5, 10, 9]. Passa (a, b) => a - b.
In Lua e R, gli array iniziano da 1, quindi entrambi gli indici iniziano da 1 e i limiti usano <=.

Domande frequenti4

Qual è la complessità temporale della fusione di due array ordinati?

Con due puntatori è O(m + n), dove m e n sono le due lunghezze. A ogni passaggio viene inserito un valore e nessun valore viene esaminato due volte. Concatenare e ordinare costa invece O((m + n) log(m + n)).

Come si uniscono sul posto due array ordinati?

Quando il primo array ha spazio sufficiente in fondo per entrambi, riempilo partendo dalla fine. Confronta i valori rimanenti più grandi dei due array, scrivi quello più grande nell'ultimo spazio libero e spostati a sinistra. Scrivere partendo dalla fine non sovrascrive mai un valore del primo array che non è ancora stato posizionato, quindi non serve un secondo array.

Unire due array ordinati è la stessa cosa della fase di unione del merge sort?

Sì. Merge sort divide un array a metà, ordina ciascuna metà e poi unisce le due metà ordinate usando esattamente questo ciclo con due puntatori. Scegliere il valore a sinistra in caso di parità mantiene i valori uguali nel loro ordine originale, ed è questo che rende stabile merge sort.

Perché non concatenare gli array e chiamare sort?

Fornisce la risposta corretta e, nella pratica, spesso è veloce. Ma ignora il fatto che gli input sono già ordinati e comporta un fattore log aggiuntivo. In un colloquio, la fusione con due puntatori è la risposta attesa, perché dimostra che sai sfruttare l’ordine che ti è stato fornito.

Python

def merge(nums1, nums2):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

nums1 = [1, 4, 9]
nums2 = [2, 3, 10]

Atteso

[1, 2, 3, 4, 9, 10]