Quitar duplicados de una lista ordenada
La misión
Problema
Recibes una lista de enteros ordenada de forma no decreciente, así que los valores iguales quedan juntos en bloques consecutivos. Compacta la lista in-place (sin memoria extra) para que cada valor distinto aparezca exactamente una vez, en el orden original. Devuelve la cantidad k de valores distintos; las primeras k casillas deben contenerlos, y lo que quede después de esas casillas se ignora.
Ejemplos
Input: nums = [1, 1, 2, 3, 3, 3]
Output: 3, and nums begins with [1, 2, 3]
Input: nums = [4, 4, 4]
Output: 1, and nums begins with [4]
Por qué: un bloque largo se reduce a un solo valor
Input: nums = []
Output: 0
Por qué: caso límite: una lista vacía no conserva nada
Pistas
0 / 3
El ordenamiento ya hizo la parte difícil: un duplicado solo puede estar justo al lado de su gemelo, así que nunca tienes que buscar en toda la lista.
Mueve dos posiciones a distinta velocidad sobre la misma lista: una que revisa cada elemento y otra que marca dónde va el siguiente valor que se conserva.
Avanza la posición de lectura por la lista. Cada vez que el valor ahí sea distinto del último que conservaste, cópialo en la posición de escritura y avanza esa posición. Al final, la posición de escritura es igual a la cantidad de valores distintos.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(1)
Restricciones
- nums is sorted in non-decreasing order
- compact the list in place
Solución
Dos índices recorren la misma lista: un lector visita cada elemento y un escritor marca la casilla del siguiente valor distinto. Como en una entrada ordenada los valores iguales son adyacentes, al lector le basta comparar con el último valor conservado para detectar un bloque nuevo. Solo se copia en los límites entre bloques, así que no se reserva ninguna lista extra. El tiempo es O(n) y el espacio es O(1).
def compact_sorted(nums):
if not nums: # nothing to keep in an empty list
return 0
write = 1 # slot for the next distinct value
for read in range(1, len(nums)):
# sorted input means a new value shows up only at a run boundary
if nums[read] != nums[write - 1]:
nums[write] = nums[read]
write += 1
return write
a = [1, 1, 2, 3, 3, 3]
print(compact_sorted(a), a[:3]) # -> 3 [1, 2, 3]
b = [4, 4, 4]
print(compact_sorted(b), b[:1]) # -> 1 [4]
print(compact_sorted([])) # -> 0¿Lo que te frena es la idea y no el código? Dos punteros lo explica.