Move Zeroes

Q: Come si spostano gli zeri alla fine senza cambiare l’ordine degli altri elementi?

Mantieni un indice write per la prossima posizione libera all’inizio e scorri con un secondo indice. Ogni valore diverso da zero che trovi viene scambiato con quello nella posizione write , che avanza di un passo verso destra. I valori vengono posizionati nell’ordine in cui li trovi, quindi il loro ordine relativo non cambia mai.

FacileDue puntatori

+10

Ti viene fornito un array di numeri interi nums. Sposta ogni 0 alla fine dell’array e mantieni gli altri valori nell’ordine in cui si trovavano. Restituisci l’array riordinato, che ha la stessa lunghezza di nums.

Funzione

moveZeroes(nums: integer-array) → integer-array

numsinteger-array: l'array di numeri interi da riordinare
Restituisceinteger-array: nums con i valori diversi da zero prima, nel loro ordine originale, e tutti gli 0 alla fine

Vincoli

1 ≤ nums.length ≤ 5000
-10⁵ ≤ nums[i] ≤ 10⁵

Esempi

Input: nums = [0, 4, 0, 7, 2]
Output: [4, 7, 2, 0, 0]
Spiegazione: I valori che non sono 0 sono 4, 7 e 2, e mantengono quest’ordine all’inizio. I due 0 occupano gli ultimi due posti.

+14 test nascosti all’invio

Per approfondire

Riesci invece a spostare tutti gli 0 all’inizio, mantenendo gli altri valori nel loro ordine, con una sola passata e usando O(1) memoria aggiuntiva?

Suggerimenti

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

0 di 3 aperti

Soluzione

Spostare gli zeri alla fine non è la parte difficile. La difficoltà sta nel mantenere gli altri valori nel loro ordine originale, e questo esclude lo scambio di ogni 0 con l’ultimo elemento. Dividi l’array in una zona iniziale che contiene i valori diversi da zero trovati finora e nel resto. Un indice legge ogni elemento, un secondo segna dove deve andare il prossimo valore diverso da zero e un unico passaggio completa il lavoro direttamente nell’array.

Copia i valori diversi da zero

Intuizione

Crea un nuovo array. Scorri nums e copia ogni valore diverso da 0, nell’ordine in cui lo incontri. Poi aggiungi degli zeri finché il nuovo array non è lungo quanto nums. Il numero di zeri che aggiungi è il numero di valori che hai saltato.

Per [0, 4, 0, 7, 2], il passaggio di copia produce [4, 7, 2], e due zeri lo trasformano in [4, 7, 2, 0, 0]. L’ordine è corretto perché copi i valori nell’ordine in cui li leggi.

Ogni elemento viene letto una volta e scritto una volta, quindi il tempo è O(n). Il secondo array richiede O(n) di memoria, che il prossimo approccio evita.

Algoritmo

Crea un array dei risultati vuoto.
Per ogni valore in nums, aggiungilo ai risultati se non è 0.
Aggiungi zeri finché i risultati non hanno tante voci quante nums.
Restituisci i risultati.

def moveZeroes(nums):
    result = [x for x in nums if x != 0]
    result += [0] * (len(nums) - len(result))
    return result

Due puntatori, scambio in loco

Intuizione

Usa due indici. read visita ogni elemento da sinistra a destra. write indica dove deve trovarsi il prossimo valore non nullo. Dopo ogni passaggio, valgono due condizioni: tutto ciò che precede write contiene i valori non nulli incontrati finora, nel loro ordine originale, e tutto ciò che si trova da write fino a read è 0.

Quando nums[read] non è 0, scambialo con nums[write] e sposta write di un passo a destra. Il valore che finisce in corrispondenza di read è uno 0 della zona degli zeri, oppure lo stesso valore quando i due indici sono uguali. I valori non nulli saltano solo gli zeri, mai gli uni sugli altri, quindi il loro ordine viene mantenuto.

Con [0, 4, 0, 7, 2]: il 4 all’indice 1 viene scambiato con l’indice 0, ottenendo [4, 0, 0, 7, 2]. Il 7 all’indice 3 viene scambiato con l’indice 1, ottenendo [4, 7, 0, 0, 2]. Il 2 all’indice 4 viene scambiato con l’indice 2, ottenendo [4, 7, 2, 0, 0]. Un solo passaggio e nessun secondo array: tempo O(n) e memoria O(1).

Algoritmo

Imposta write su 0.
Sposta read dal primo indice all'ultimo.
Se nums[read] non è 0, scambia nums[read] con nums[write], poi aggiungi 1 a write.
Restituisci nums.

def moveZeroes(nums):
    write = 0  # nums[:write] holds the non-zero values found so far, in order
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1
    return nums

Trappole e casi limite

I bug più comuni o alterano l'ordine degli altri valori o saltano degli elementi.

Scambiare ogni 0 con l'ultimo elemento sposta gli zeri, ma rimescola il resto: [0, 4, 7] diventa [7, 4, 0].
Eliminare gli zeri dall'array mentre un indice lo attraversa fa saltare degli elementi. In [0, 0, 5], eliminando l'indice 0, il secondo 0 scivola all'indice 0 mentre il ciclo passa all'indice 1. Ogni eliminazione sposta anche il resto dell'array, rendendo il ciclo O(n²).
Verifica x != 0, non x > 0. I valori negativi non sono zeri: [-1, 0, -2] deve diventare [-1, -2, 0], ma con x > 0 la versione che copia restituisce [0, 0, 0].
Un array senza zeri o contenente solo zeri deve rimanere invariato. Nella versione con scambio, read e write restano uguali fino al primo 0, quindi quegli scambi non cambiano nulla.
In Lua e R, gli array iniziano da 1, quindi anche write inizia da 1.

Domande frequenti4

Qual è la complessità temporale di Move Zeroes?

O(n). Entrambi gli approcci leggono ogni elemento una volta. Copiare i valori diversi da zero in un nuovo array richiede O(n) di memoria aggiuntiva, mentre lo scambio con due puntatori opera all'interno dell'array con O(1) di memoria aggiuntiva.

Come si spostano gli zeri alla fine senza cambiare l’ordine degli altri elementi?

Mantieni un indice write per la prossima posizione libera all’inizio e scorri con un secondo indice. Ogni valore diverso da zero che trovi viene scambiato con quello nella posizione write, che avanza di un passo verso destra. I valori vengono posizionati nell’ordine in cui li trovi, quindi il loro ordine relativo non cambia mai.

È possibile risolvere Move Zeroes con meno scritture?

Sì. Invece di scambiare, copia ogni valore diverso da zero in nums[write] e, dopo la scansione, riempi ogni posizione da write fino alla fine con 0. In questo modo scrivi in ogni posizione al massimo una volta. Puoi anche evitare lo scambio quando read è uguale a write, perché rimetterebbe un valore dove si trova già.

Perché Move Zeroes è un problema a due puntatori?

Un puntatore legge ogni elemento e l’altro segna la fine della parte iniziale completata. Entrambi si muovono solo in avanti, quindi insieme effettuano un’unica passata. Lo stesso schema di lettura e scrittura rimuove i duplicati da un array ordinato o filtra qualsiasi valore da un array sul posto.

Python

def moveZeroes(nums):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

nums = [0, 4, 0, 7, 2]

Atteso

[4, 7, 2, 0, 0]