Find the Duplicate Number

Q: ¿Cuál es la complejidad temporal de Find the Duplicate Number?

La detección de ciclos de Floyd se ejecuta en tiempo O(n) y usa O(1) de memoria adicional: cada una de sus dos fases sigue como máximo unos pocos múltiplos de n enlaces. La búsqueda binaria en los valores toma un tiempo de O(n log n) y usa O(1) de memoria. Comparar cada par es O(n²) .

Q: ¿Por qué no usar un conjunto hash o ordenar el arreglo?

Ambos encuentran la respuesta en tiempo O(n) o O(n log n) , y en un programa real cualquiera de los dos estaría bien. La tarea los prohíbe a propósito: un conjunto hash usa memoria adicional O(n) , y ordenar modifica nums o requiere una copia completa. Las restricciones son lo que te lleva a considerar la perspectiva de los ciclos.

Q: ¿Por qué no funciona la fórmula de la suma para encontrar el número duplicado?

Restar 1 + 2 + ... + n de la suma del arreglo da el duplicado solo cuando aparece exactamente dos veces y todos los demás valores aparecen una vez. Aquí, el valor repetido puede aparecer muchas veces y reemplazar valores faltantes. En [4, 2, 4, 1, 4] , la diferencia es 15 menos 10 = 5, que ni siquiera está en el arreglo.

MedioPunteros rápido y lento Búsqueda binaria

+10

Recibes un arreglo nums de n+1 enteros, cada uno entre 1 y n. Exactamente un valor aparece más de una vez, posiblemente muchas veces, y devuelves ese valor.

Resuélvelo sin cambiar nums y usando solo una cantidad constante de memoria adicional.

Función

findDuplicate(nums: integer-array) → integer

numsinteger-array: n+1 enteros, cada uno entre 1 y n
Devuelveinteger: el valor que aparece más de una vez

Restricciones

1 ≤ n ≤ 10⁴
nums.length == n+1
1 ≤ nums[i] ≤ n
Exactamente un valor aparece dos o más veces; todos los demás valores aparecen como máximo una vez.

Ejemplos

Entrada: nums = [2, 5, 1, 3, 5, 4]
Salida: 5
Explicación: Aquí n es 5, y el 5 aparece en las posiciones 1 y 4, así que la respuesta es 5. Todos los demás valores del 1 al 5 aparecen una vez.

+17 pruebas ocultas al enviar

Para ir más allá

La búsqueda binaria sobre valores mantiene ambas reglas en tiempo O(n log n). ¿Puedes mantenerlas en tiempo O(n)?

Pistas

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

0 de 3 abiertas

Solución

Un conjunto hash o una ordenación encuentra el valor repetido de inmediato, pero ambas opciones incumplen las reglas: el conjunto necesita memoria para cada valor y la ordenación modifica nums. La solución está en los números. Cada valor está entre 1 y n, así que también es una posición válida del arreglo. Lee cada valor como un enlace a otra posición, y seguir los enlaces desde la posición 0 siempre termina en un ciclo cuya entrada es el duplicado. Los punteros rápido y lento de Floyd encuentran esa entrada usando dos enteros.

Compara cada par

Correcto, pero no termina con las pruebas más grandes

Intuición

El valor repetido aparece al menos en dos posiciones i < j. Compara cada posición con todas las posiciones posteriores; el primer par que contiene valores iguales da la respuesta. En el primer ejemplo, la posición 1 contiene 5, y el recorrido desde la posición 2 en adelante encuentra otro 5 en la posición 4.

Así se mantienen ambas reglas: no se escribe nada y la única memoria son dos contadores de bucle. Es lento porque compara pares. Con n+1 = 10,001 valores y ambas copias cerca del final, comprueba aproximadamente 5 × 10^7 pares.

Algoritmo

Para cada posición i desde 0 hasta el final:
Para cada posición j después de i, compara nums[i] con nums[j].
Devuelve nums[i] en la primera coincidencia.

def findDuplicate(nums):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] == nums[j]:
                return nums[i]
    return -1  # unreachable: the input always holds a repeat

Búsqueda binaria por valor

Intuición

Busca en el rango de valores, no en las posiciones. Elige un límite m y cuenta cuántas entradas de nums son menores o iguales que m.

Si el duplicado d es mayor que m, los valores del 1 al m aparecen como máximo una vez cada uno, así que el recuento es como máximo m. Si d es menor o igual que m, cada valor mayor que m aparece como máximo una vez, así que como máximo n-m entradas son mayores que m y al menos m+1 son menores o iguales que m. Por tanto, la prueba "count > m" es falsa para todo m menor que d y verdadera desde d en adelante. La búsqueda binaria encuentra el primer m para el que se vuelve verdadera, y ese es d.

En el segundo ejemplo, n es 4. Para m = 2, las entradas 2 y 1 dan un recuento de 2, que no es mayor que 2, así que la respuesta es mayor que 2. Para m = 3, el recuento sigue siendo 2, así que la respuesta es 4. Cada ronda lee todo el arreglo una vez y reduce a la mitad el rango, así que el trabajo es O(n log n): unas 14 pasadas por 10,001 valores.

Algoritmo

Establece low = 1 y high = n, la longitud de nums menos uno.
Mientras low < high, toma mid a medio camino entre ambos.
Cuenta las entradas de nums que son como máximo mid.
Si el recuento es mayor que mid, establece high = mid; de lo contrario, establece low = mid+1.
Devuelve low.

def findDuplicate(nums):
    low, high = 1, len(nums) - 1
    while low < high:
        mid = (low + high) // 2
        # How many values fall in 1..mid?
        count = 0
        for x in nums:
            if x <= mid:
                count += 1
        if count > mid:
            high = mid      # 1..mid holds more values than it has room for
        else:
            low = mid + 1   # the repeat is above mid
    return low

Detección de ciclos de Floyd en los enlaces de valores

Intuición

Lee el arreglo como enlaces: la posición i apunta a la posición nums[i]. Cada posición de 0 a n tiene exactamente un enlace saliente, y cada enlace llega a algún lugar entre 1 y n. En el primer ejemplo, los enlaces son 0 → 2, 1 → 5, 2 → 1, 3 → 3, 4 → 5 y 5 → 4.

Empieza en la posición 0 y sigue los enlaces. El recorrido nunca puede detenerse, porque cada posición tiene un enlace y solo hay n+1 posiciones, así que necesariamente volverá a una posición que ya visitó. A partir de entonces, dará vueltas para siempre. El recorrido es una cola seguida de un ciclo, con forma de la letra ρ. En el primer ejemplo, el recorrido es 0, 2, 1, 5, 4, 5, 4, y así sucesivamente: la cola es 0, 2, 1 y el ciclo es 5, 4. La posición 3 apunta a sí misma, pero el recorrido nunca llega a ella, y eso no causa ningún problema.

La entrada del ciclo es el duplicado. El recorrido llega a 5 dos veces desde lugares diferentes: una vez desde el final de la cola (la posición 1, porque nums[1] es 5) y otra desde el final del ciclo (la posición 4, porque nums[4] es 5). Dos posiciones diferentes contienen el valor 5, así que 5 se repite. La cola siempre contiene la posición 0, porque ningún valor es 0 y nada vuelve a apuntar a ella, así que la entrada siempre tiene estas dos formas diferentes de llegar a ella. Exactamente un valor se repite, así que la entrada es ese valor.

Ahora encuentra la entrada con dos punteros, como en la detección de ciclos en listas enlazadas. En la fase 1, slow sigue un enlace por ronda y fast sigue dos, hasta que se encuentran en la misma posición en algún lugar del ciclo. En el primer ejemplo, se encuentran en 4. En la fase 2, vuelve a poner slow en 0, deja fast donde está y mueve ambos un enlace por ronda. Se encuentran en la entrada.

Por qué funciona la fase 2: supongamos que la cola requiere T enlaces para llegar a la entrada y que el ciclo tiene C posiciones. Cuando los punteros se encontraron, slow había dado s pasos y fast, 2s. Ambos estaban en el mismo lugar, así que los s pasos adicionales de fast eran vueltas completas del ciclo. Después de T pasos más, slow llega a la entrada desde 0, y fast está donde estaría un recorrido desde 0 después de s+T pasos, porque sus vueltas adicionales no cambian nada. Eso equivale a T pasos hasta la entrada más s pasos, un número entero de vueltas, lo que también lo deja en la entrada. No pueden encontrarse antes, porque slow todavía está en la cola y fast nunca sale del ciclo. En el primer ejemplo, slow avanza por 2, 1, 5 mientras fast avanza por 5, 4, 5, y se encuentran en 5 después de T = 3 pasos.

Cada fase requiere O(n) pasos, la única memoria utilizada son dos posiciones y nunca se modifica nums.

Algoritmo

Trata cada posición i como un nodo que enlaza con la posición nums[i], e inicia ambos punteros en la posición 0.
Fase 1: mueve slow a nums[slow] y fast a nums[nums[fast]] hasta que sean iguales.
Fase 2: vuelve a establecer slow en 0.
Mueve ambos un enlace a la vez: slow a nums[slow] y fast a nums[fast], hasta que sean iguales.
Devuelve esa posición: es el valor repetido.

def findDuplicate(nums):
    # Treat each index i as a node with one link, to nums[i].
    # Phase 1: slow moves one link, fast moves two, until they meet in the cycle.
    slow = fast = 0
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    # Phase 2: restart one pointer at index 0 and move both one link at a time.
    # They meet at the cycle's entrance, the index two positions link to.
    slow = 0
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

Errores comunes y casos límite

La mayoría de las respuestas incorrectas se deben a confundir las posiciones con los valores o a detenerse una fase antes en el método de Floyd.

Devolver el punto de encuentro de la fase 1. Es una posición del ciclo, no necesariamente la entrada. En el primer ejemplo, los punteros se encuentran en 4, pero la respuesta es 5.
Comprobar slow == fast antes del primer movimiento. Ambos empiezan en 0, así que el ciclo termina de inmediato. Muévelos primero y después compáralos, o empieza con uno y dos enlaces de ventaja.
Empezar el recorrido en cualquier posición que no sea 0. Ningún enlace apunta a la posición 0, ya que ningún valor es 0, y eso es lo que garantiza una cola. Empezar en otra posición puede llevarte a un ciclo sin forma de entrar desde fuera, como la posición 3 en el primer ejemplo, cuya entrada no demuestra nada.
Suponer que el duplicado aparece exactamente dos veces. El truco de la suma, el total menos 1 + 2 + ... + n, da 15 menos 10 = 5 en el segundo ejemplo, pero la respuesta es 4. Lo mismo ocurre con los trucos de XOR.
Hacer una búsqueda binaria sobre las posiciones en vez de los valores, o comprobar count >= mid. La cantidad de valores menores o iguales que m es exactamente m cuando ningún valor de 1 a m se repite y no falta ninguno, así que solo > separa los dos lados.
Marcar los valores visitados negando nums[x] o intercambiando los valores para colocarlos en su sitio. Ambos métodos funcionan, pero los dos modifican el arreglo, lo cual está prohibido por la tarea.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Find the Duplicate Number?

La detección de ciclos de Floyd se ejecuta en tiempo O(n) y usa O(1) de memoria adicional: cada una de sus dos fases sigue como máximo unos pocos múltiplos de n enlaces. La búsqueda binaria en los valores toma un tiempo de O(n log n) y usa O(1) de memoria. Comparar cada par es O(n²).

¿Por qué la detección de ciclos de Floyd encuentra el número duplicado?

Si lees cada valor como un enlace desde su posición hasta la posición que nombra, el recorrido desde la posición 0 debe terminar en un ciclo, porque nunca se detiene y solo tiene n+1 lugares adonde ir. Se llega a la posición donde entra en el ciclo desde dos posiciones distintas, una en la cola y otra en el ciclo, así que dos entradas contienen ese valor. El método de Floyd encuentra la entrada de un ciclo con dos punteros, por lo que encuentra el valor repetido.

¿Por qué no usar un conjunto hash o ordenar el arreglo?

Ambos encuentran la respuesta en tiempo O(n) o O(n log n), y en un programa real cualquiera de los dos estaría bien. La tarea los prohíbe a propósito: un conjunto hash usa memoria adicional O(n), y ordenar modifica nums o requiere una copia completa. Las restricciones son lo que te lleva a considerar la perspectiva de los ciclos.

¿Por qué no funciona la fórmula de la suma para encontrar el número duplicado?

Restar 1 + 2 + ... + n de la suma del arreglo da el duplicado solo cuando aparece exactamente dos veces y todos los demás valores aparecen una vez. Aquí, el valor repetido puede aparecer muchas veces y reemplazar valores faltantes. En [4, 2, 4, 1, 4], la diferencia es 15 menos 10 = 5, que ni siquiera está en el arreglo.

Python

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

Casos de prueba

Caso 1

Caso 2

Entrada

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

Esperado

Find the Duplicate Number

Función

Restricciones

Ejemplos

Pistas

Solución

Compara cada par

Búsqueda binaria por valor

Detección de ciclos de Floyd en los enlaces de valores

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares