Remove Duplicates from Sorted Array

Q: ¿Cómo eliminas los duplicados in situ sin memoria adicional?

Mantén un índice de escritura k junto al índice de lectura. Las primeras posiciones k contienen los valores distintos encontrados hasta el momento. Cuando el valor que lees es distinto de nums[k-1] , cópialo en nums[k] y avanza k . El índice de escritura nunca supera al índice de lectura, así que nada se sobrescribe antes de leerse.

FácilDos punteros

+10

Recibes un arreglo de enteros nums ordenado en orden no decreciente, por lo que los valores iguales están uno junto al otro. Devuelve los valores distintos de nums, cada uno una sola vez, en el orden en que aparecen. Por ejemplo, [2, 2, 5] da [2, 5].

Función

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

numsinteger-array: los números enteros, ordenados de menor a mayor
Devuelveinteger-array: los valores distintos de nums, en orden creciente

Restricciones

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
nums está ordenado en orden no decreciente.

Ejemplos

Entrada: nums = [1, 1, 2, 3, 3, 3]
Salida: [1, 2, 3]
Explicación: 1 aparece dos veces y 3 tres veces. Al conservar uno de cada uno, queda [1, 2, 3].

Entrada: nums = [-2, 0, 0, 5]
Salida: [-2, 0, 5]
Explicación: Solo se repite 0. Los valores negativos funcionan de la misma manera, así que la respuesta es [-2, 0, 5].

Entrada: nums = [7, 7, 7]
Salida: [7]
Explicación: Todos los valores son 7, así que solo queda un 7.

+15 pruebas ocultas al enviar

Para ir más allá

¿Puedes hacerlo con memoria adicional O(1), reescribiendo nums en el mismo lugar en vez de crear un segundo arreglo?

Pistas

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

0 de 3 abiertas

Solución

Eliminar duplicados de un arreglo arbitrario significa recordar cada valor que has visto. Una entrada ordenada elimina esa necesidad: las copias de un valor son vecinas, así que un valor es nuevo exactamente cuando difiere del último que conservaste. Eso convierte la tarea en un solo recorrido con dos índices y sin memoria adicional.

Recuerda los valores vistos en un conjunto hash

Intuición

Recorre nums y mantén un conjunto de los valores que ya hayas añadido a la respuesta. Cuando un valor no esté en el conjunto, añádelo al final de la respuesta y agrégalo al conjunto; cuando sí esté, omítelo. Para [1, 1, 2, 3, 3, 3], la respuesta crece hasta [1], después [1, 2], después [1, 2, 3], y se omiten todas las copias posteriores.

Cada valor se añade la primera vez que aparece y nunca más, en el orden en que lo encuentras, así que la respuesta es correcta. Este enfoque nunca aprovecha que nums esté ordenado; funcionaría con cualquier arreglo.

Las búsquedas en un conjunto tardan O(1) en promedio, así que el recorrido tarda O(n), pero tanto el conjunto como la respuesta pueden contener n valores: espacio adicional O(n). En C, al no haber un conjunto integrado, un arreglo de indicadores para los 2 × 10^4 + 1 valores posibles hace el mismo trabajo.

Algoritmo

Crea un conjunto vacío seen y una lista vacía result.
Para cada valor de nums, comprueba si está en seen.
Si no está, añádelo a seen y agrégalo a result.
Devuelve result.

def removeDuplicates(nums):
    seen = set()
    result = []
    for num in nums:
        if num not in seen:
            seen.add(num)
            result.append(num)
    return result

Compacta en el mismo lugar con un puntero de escritura

Intuición

En una entrada ordenada, todas las copias de un valor forman una secuencia, así que un valor es nuevo exactamente cuando es distinto del último valor que conservaste. Eso requiere una comparación, no un conjunto.

Usa dos índices. El índice de lectura i recorre todos los valores. El índice de escritura k marca el final de la parte conservada: nums[0] a nums[k-1] siempre contiene los valores distintos encontrados hasta el momento. Empieza con k = 1, ya que el primer valor siempre se conserva. Cuando nums[i] es distinto de nums[k-1], cópialo en nums[k] y avanza k.

Con [1, 1, 2, 3, 3, 3]: i = 1 lee un segundo 1 y no ocurre nada. i = 2 lee 2, que es distinto de nums[0] = 1, así que se coloca en el índice 1 y k pasa a ser 2. i = 3 escribe 3 en el índice 2 y k pasa a ser 3. Los dos últimos 3 coinciden con nums[2] y se omiten. Ahora, las tres primeras posiciones contienen [1, 2, 3].

La escritura nunca sobrepasa la lectura, porque k siempre es menor o igual que i, así que nunca sobrescribes un valor antes de leerlo. Una pasada requiere un tiempo de O(n) y, aparte de los valores devueltos, usas dos enteros: espacio extra de O(1).

Algoritmo

Establece k = 1: siempre se conserva nums[0].
Recorre i desde 1 hasta el último índice.
Si nums[i] es diferente de nums[k-1], establece nums[k] = nums[i] y suma 1 a k.
Devuelve los primeros k valores de nums.

def removeDuplicates(nums):
    # nums[0:k] holds the distinct values found so far, in order.
    k = 1
    for i in range(1, len(nums)):
        if nums[i] != nums[k - 1]:
            nums[k] = nums[i]
            k += 1
    return nums[:k]

Errores comunes y casos límite

El puntero de escritura es corto, y sus errores tienen que ver con qué valor comparas.

Comparar nums[i] con nums[i+1] mientras i llega hasta el último índice. La última comparación lee una posición más allá del final del array.
Empezar k en 0. Entonces, el primer valor se compara con nums[-1], que está fuera de rango o, en Python, es el último elemento.
Devolver el array completo en lugar de sus primeros k valores. La parte final todavía contiene los valores antiguos, así que [1, 1, 2] se devolvería como [1, 2, 2].
Construir la respuesta iterando sobre un conjunto hash. En la mayoría de los lenguajes, un conjunto hash no mantiene ningún orden, así que los valores pueden salir desordenados; en su lugar, añade cada valor a una lista cuando lo encuentres por primera vez.
En Lua y R, los arrays empiezan en 1. La parte conservada va de nums[1] a nums[k], y la comparación es con nums[k], no con nums[k-1].

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Eliminar duplicados de un array ordenado?

La solución con puntero de escritura lee cada valor una vez, por lo que se ejecuta en tiempo O(n). Además de los valores que devuelve, usa espacio adicional O(1): dos índices.

¿Por qué es necesario ordenar el arreglo?

La ordenación coloca todas las copias de un valor en una misma secuencia, así que un valor es nuevo exactamente cuando difiere del último valor conservado. En un arreglo sin ordenar, una copia puede aparecer muy lejos de la primera, y necesitas un conjunto hash para recordar cada valor visto, lo que cuesta O(n) de espacio adicional.

¿Cómo eliminas los duplicados in situ sin memoria adicional?

Mantén un índice de escritura k junto al índice de lectura. Las primeras posiciones k contienen los valores distintos encontrados hasta el momento. Cuando el valor que lees es distinto de nums[k-1], cópialo en nums[k] y avanza k. El índice de escritura nunca supera al índice de lectura, así que nada se sobrescribe antes de leerse.

¿Cómo permitirías que cada valor aparezca como máximo dos veces?

Compara con el valor que está dos posiciones atrás en la parte conservada en lugar de una: copia nums[i] cuando k < 2 o cuando sea distinto de nums[k-2]. Si es igual a nums[k-2], la parte conservada ya termina con dos copias de ese valor. La misma idea permite como máximo m copias con nums[k-m].

Python

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

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

nums = [1, 1, 2, 3, 3, 3]

Esperado

[1, 2, 3]