Mover el valor objetivo al final
La misión
Problema
Un editor de playlists quiere mover al final de la cola todas las copias de un id de canción sin desordenar nada más. Dada una lista nums y un valor v, reorganiza la lista in-place (sin memoria extra) para que los elementos distintos de v conserven su orden relativo original al frente y todas las copias de v queden al fondo. Devuelve el mismo objeto lista y usa solo una cantidad constante de memoria extra.
Ejemplos
Input: nums = [4, 0, 7, 0, 2], v = 0
Output: [4, 7, 2, 0, 0]
Por qué: 4, 7 y 2 mantienen el orden en que llegaron
Input: nums = [3, 1, 3, 3, 5], v = 3
Output: [1, 5, 3, 3, 3]
Por qué: las tres copias de 3 se juntan al fondo
Input: nums = [], v = 9
Output: []
Por qué: caso límite: no hay nada que mover
Pistas
0 / 3
Construir una segunda lista con los valores que se quedan y otra con las copias funciona, pero la tarea pide memoria extra constante. Piensa dónde debería caer el siguiente valor que se queda.
Usa dos índices sobre la misma lista: uno que lee cada elemento y otro que marca la casilla donde se escribirá el siguiente valor que se queda.
Lee de izquierda a derecha y copia cada elemento distinto de v en la casilla de escritura, avanzando el índice de escritura cada vez. Cuando el lector termine, llena con v todas las casillas desde el índice de escritura hasta el final.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(1)
Restricciones
- rearrange in place with O(1) extra memory
- other values keep their relative order
Solución
El índice de escritura solo avanza cuando se copia un valor que se queda, así que nunca adelanta al lector y ningún valor que se queda se sobrescribe antes de haberse leído. Copiar en el orden de lectura conserva gratis el orden relativo de esos valores. Cada casilla después del último valor que se queda debe tener una copia de v, porque la cantidad de copias es igual a la cantidad de casillas sobrantes. El tiempo es O(n) con una pasada más el llenado, y el espacio es O(1).
def push_back(nums, v):
write = 0 # slot for the next value we keep in front
for x in nums:
if x != v:
nums[write] = x # copy forward, order is preserved
write += 1
for i in range(write, len(nums)):
nums[i] = v # the leftover slots belong to v
return nums
print(push_back([4, 0, 7, 0, 2], 0)) # -> [4, 7, 2, 0, 0]
print(push_back([3, 1, 3, 3, 5], 3)) # -> [1, 5, 3, 3, 3]
print(push_back([], 9)) # -> []¿Lo que te frena es la idea y no el código? Move Zeroes lo explica.