Move Zeroes

Q: ¿Cómo puedes mover los ceros al final sin cambiar el orden de los demás elementos?

Mantén un índice write para la siguiente posición libre al principio y recorre la lista con un segundo índice. Cada valor distinto de cero que encuentres se intercambia con el que está en la posición write , y write avanza un paso a la derecha. Los valores se colocan en el orden en que los encuentras, así que su orden relativo nunca cambia.

FácilDos punteros

+10

Recibes un arreglo de números enteros nums. Mueve todos los 0 al final del arreglo y conserva los demás valores en el orden en que estaban. Devuelve el arreglo reorganizado, que tiene la misma longitud que nums.

Función

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

numsinteger-array: el arreglo de enteros que se debe reorganizar
Devuelveinteger-array: los números con los valores distintos de cero primero, en su orden original, y todos los 0 al final

Restricciones

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

Ejemplos

Entrada: nums = [0, 4, 0, 7, 2]
Salida: [4, 7, 2, 0, 0]
Explicación: Los valores que no son 0 son 4, 7 y 2, y mantienen ese orden al principio. Los dos 0 ocupan los dos últimos lugares.

+14 pruebas ocultas al enviar

Para ir más allá

¿Puedes mover todos los 0 al principio y mantener los demás valores en su orden, en una sola pasada y con memoria adicional O(1)?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Llevar los ceros al final no es la parte difícil. Lo difícil es mantener los demás valores en su orden original, y eso descarta intercambiar cada 0 con el último elemento. Divide el array en una zona delantera que contenga los valores distintos de cero encontrados hasta el momento y el resto. Un índice lee cada elemento, un segundo marca dónde debe ir el siguiente valor distinto de cero y una sola pasada termina el trabajo en el mismo lugar.

Copiar los valores distintos de cero

Intuición

Crea un nuevo arreglo. Recorre nums y copia cada valor que no sea 0, en el orden en que lo encuentres. Después, agrega ceros hasta que el nuevo arreglo tenga la misma longitud que nums. La cantidad de ceros que agregues es igual a la cantidad que omitiste.

Para [0, 4, 0, 7, 2], el paso de copia da [4, 7, 2], y dos ceros lo convierten en [4, 7, 2, 0, 0]. El orden es correcto porque copias los valores en el orden en que los lees.

Cada elemento se lee una vez y se escribe una vez, así que el tiempo es O(n). El segundo arreglo requiere O(n) de memoria, algo que el siguiente enfoque evita.

Algoritmo

Crea un array de resultados vacío.
Para cada valor de nums, añádelo al resultado si no es 0.
Añade ceros hasta que el resultado tenga tantas entradas como nums.
Devuelve el resultado.

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

Dos punteros, intercambio in situ

Intuición

Usa dos índices. read recorre todos los elementos de izquierda a derecha. write marca dónde debe ir el siguiente valor distinto de cero. Después de cada paso, se cumplen dos condiciones: todo lo que está antes de write son los valores distintos de cero vistos hasta el momento, en su orden original, y todo lo que está desde write hasta read es 0.

Cuando nums[read] no es 0, intercámbialo con nums[write] y mueve write un paso a la derecha. El valor que queda en read es un 0 de la zona de ceros, o el mismo valor cuando los dos índices son iguales. Los valores distintos de cero solo saltan sobre ceros, nunca unos sobre otros, por lo que se conserva su orden.

Con [0, 4, 0, 7, 2]: el 4 del índice 1 se intercambia con el índice 0, dando [4, 0, 0, 7, 2]. El 7 del índice 3 se intercambia con el índice 1, dando [4, 7, 0, 0, 2]. El 2 del índice 4 se intercambia con el índice 2, dando [4, 7, 2, 0, 0]. Una pasada y ningún segundo array: tiempo O(n) y memoria O(1).

Algoritmo

Establece write en 0.
Mueve read del primer índice al último.
Si nums[read] no es 0, intercambia nums[read] con nums[write], después suma 1 a write.
Devuelve 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

Errores comunes y casos límite

Los errores habituales alteran el orden de los demás valores o se saltan elementos.

Intercambiar cada 0 con el último elemento mueve los ceros, pero desordena el resto: [0, 4, 7] se convierte en [7, 4, 0].
Eliminar ceros del arreglo mientras un índice lo recorre hace que se salten elementos. En [0, 0, 5], eliminar el índice 0 desplaza el segundo 0 al índice 0 mientras el bucle avanza al índice 1. Cada eliminación también desplaza el resto del arreglo, lo que hace que el bucle sea O(n²).
Comprueba x != 0, no x > 0. Los valores negativos no son ceros: [-1, 0, -2] debe convertirse en [-1, -2, 0], pero con x > 0 la versión que copia devuelve [0, 0, 0].
Un arreglo sin ceros, o con solo ceros, debe permanecer sin cambios. En la versión con intercambios, read y write siguen siendo iguales hasta el primer 0, por lo que esos intercambios no cambian nada.
En Lua y R, los arreglos empiezan en 1, así que write también empieza en 1.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Move Zeroes?

O(n). Ambos enfoques leen cada elemento una vez. Copiar los valores distintos de cero en un nuevo arreglo requiere O(n) de memoria adicional, mientras que el intercambio con dos punteros se realiza dentro del arreglo con O(1) de memoria adicional.

¿Cómo puedes mover los ceros al final sin cambiar el orden de los demás elementos?

Mantén un índice write para la siguiente posición libre al principio y recorre la lista con un segundo índice. Cada valor distinto de cero que encuentres se intercambia con el que está en la posición write, y write avanza un paso a la derecha. Los valores se colocan en el orden en que los encuentras, así que su orden relativo nunca cambia.

¿Se puede resolver Mover ceros con menos escrituras?

Sí. En lugar de intercambiar, copia cada valor distinto de cero en nums[write] y, después del recorrido, rellena cada posición desde write hasta el final con 0. Así se escribe en cada posición como máximo una vez. También puedes omitir un intercambio cuando read es igual a write, ya que volvería a poner un valor donde ya está.

¿Por qué Move Zeroes es un problema de dos punteros?

Un puntero lee cada elemento y el otro marca el final de la parte inicial ya procesada. Ambos solo avanzan, así que juntos realizan un único recorrido. El mismo patrón de lectura y escritura elimina duplicados de un arreglo ordenado o filtra cualquier valor de un arreglo en el mismo lugar.

Python

def moveZeroes(nums):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado

[4, 7, 2, 0, 0]