Contains Duplicate
Se te da una matriz de números enteros nums. Devuelve true si algún valor aparece al menos dos veces y false si todos los valores son diferentes.
Función
- numsinteger-array
- los números enteros que hay que comprobar
- Devuelveboolean
- verdadero si algún valor aparece al menos dos veces, falso en caso contrario
Restricciones
1 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109
Ejemplos
- Entrada
- nums = [3, 1, 4, 1, 5]
- Salida
- true
- Explicación
- El valor
1aparece en el índice 1 y de nuevo en el índice 3, así que la respuesta estrue.
- Entrada
- nums = [2, 7, 1, 8]
- Salida
- false
- Explicación
2,7,1y8son cuatro valores diferentes, así que nada se repite.
- Entrada
- nums = [-4, 4, 0]
- Salida
- false
- Explicación
-4y4tienen el mismo valor absoluto, pero son números diferentes, y0aparece una vez, así que la respuesta esfalse.
+17 pruebas ocultas al enviar
Para ir más allá
¿Puedes detenerte en cuanto encuentres el primer valor repetido, en lugar de leer siempre todo el arreglo?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Comparar cada valor con todos los demás funciona, pero para
10^4valores eso supone alrededor de5 × 10^7comparaciones. ¿Qué podrías recordar sobre los valores que ya has recorrido?Una repetición significa que el valor actual es uno que ya has encontrado antes. Un conjunto hash responde «¿ya he encontrado este valor?» en tiempo constante en promedio.
Recorre el arreglo una vez con un conjunto vacío. Para cada valor, devuelve
truesi ya está en el conjunto; de lo contrario, añádelo. Si el bucle termina, todos los valores eran diferentes.
Solución
Una repetición es un valor con el que ya te has encontrado, y el trabajo consiste en responder rápidamente a «¿ya me he encontrado con este valor?». Comparar cada par responde a la pregunta, pero para n = 10^4 eso supone n(n-1)/2, unas 5 × 10^7 comparaciones. Ordenar coloca los valores iguales uno junto al otro, y un conjunto hash responde a la pregunta en O(1) en promedio, lo que permite hacer una sola pasada.
Ordena y luego compara los elementos vecinos
Intuición
En un arreglo ordenado, los valores iguales quedan uno al lado del otro. [3, 1, 4, 1, 5] se ordena como [1, 1, 3, 4, 5], y los dos 1 quedan ahora juntos. Así que, después de ordenar, solo comparas cada valor con el que está justo antes: n-1 comparaciones en lugar de las n(n-1)/2 que se necesitan para probar cada par.
Si no hay dos elementos vecinos iguales, no hay dos valores iguales en ninguna parte: cualquier valor entre dos copias de x en el orden ordenado tendría que ser a la vez al menos x y como máximo x, así que sería otro x.
La ordenación domina el tiempo, con O(n log n). Ordenar nums en el sitio no requiere ningún arreglo adicional, pero reordena la entrada de quien llama; si eso no está permitido, ordena una copia, lo que cuesta O(n) de espacio.
Algoritmo
- Ordena
numsen orden creciente. - Recorre
idesde 1 hasta el último índice. - Si
nums[i]es igual anums[i-1], devuelvetrue. - Después del bucle, devuelve
false.
def containsDuplicate(nums):
nums.sort()
# After sorting, equal values sit next to each other.
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
return True
return FalseUna pasada con un conjunto hash
Intuición
Recorre el arreglo una vez y guarda en un conjunto hash cada valor que hayas encontrado. Antes de añadir un valor, comprueba si ya está en el conjunto. Para [3, 1, 4, 1, 5], el conjunto crece hasta {3, 1, 4}, y cuando aparece el segundo 1, el conjunto ya lo contiene, así que devuelves true sin leer el 5.
El conjunto siempre contiene exactamente los valores anteriores a la posición actual, así que encontrar un valor significa que el valor actual apareció antes, y llegar al final sin encontrar ninguno significa que todos los valores son distintos.
Buscar e insertar en un conjunto hash toma O(1) de tiempo en promedio, así que el recorrido completo es O(n). El costo es la memoria: si no hay repeticiones, el conjunto termina conteniendo los n valores.
Algoritmo
- Crea un conjunto hash vacío
seen. - Para cada valor de
nums, si está enseen, devuelvetrue. - De lo contrario, añádelo a
seen. - Después del bucle, devuelve
false.
def containsDuplicate(nums):
seen = set()
for num in nums:
if num in seen:
return True
seen.add(num)
return False
Errores comunes y casos límite
La lógica es breve, así que los errores están en los límites de los bucles y en qué comparas.
- Comparar cada par haciendo que el bucle interno empiece en
j = i. Así, cada valor coincide consigo mismo y la respuesta siempre estrue. - Comparar valores vecinos sin ordenar primero. En
[9, 1, 2, 3, 9], los dos9no están uno junto al otro. - Empezar el bucle de vecinos en el índice 0 y leer
nums[-1]. Empieza en 1, y un arreglo con un solo valor devuelve correctamentefalse. - Tratar los valores con el mismo valor absoluto como iguales, por ejemplo, calculando un hash de
abs(x).-4y4son números distintos. - Escribir un comparador de ordenación en C que devuelva
x - y. Aquí la diferencia se mantiene dentro de±2 × 10^9, por debajo del límite deint,2^31-1 = 2147483647, así que resulta que cabe; con valores cercanos a los límites deint, se desborda y la ordenación da un resultado incorrecto. En su lugar, devuelve(x > y) - (x < y).
Preguntas frecuentes4
¿Cuál es la complejidad temporal de Contains Duplicate?
La solución con un conjunto hash se ejecuta en O(n) de tiempo en promedio y usa O(n) de espacio adicional. Ordenar primero toma O(n log n) de tiempo y no requiere un arreglo adicional si puedes reordenar la entrada. Comparar cada par toma O(n²) de tiempo.
¿Puedes resolver Contains Duplicate sin espacio adicional?
Sí, si puedes reordenar el arreglo: ordénalo en el mismo lugar y compara cada valor con el vecino. Eso cambia el conjunto de O(n) por un tiempo de O(n log n). Sin reordenar y sin memoria adicional, la única opción que queda es comprobar los pares en O(n²).
¿Por qué un conjunto hash hace que la comprobación sea rápida?
Un conjunto hash almacena valores según su hash, por lo que preguntar si contiene un valor lleva un tiempo constante en promedio, en lugar de tener que recorrerlo. Cada elemento requiere una búsqueda y una inserción, lo que hace que el recorrido completo sea lineal.
¿Es una solución válida comparar el tamaño del conjunto con la longitud del array?
Sí. Crear un conjunto con todos los elementos de nums y comprobar si es más pequeño que el arreglo da la respuesta correcta en tiempo O(n). La versión con un bucle suele ser mejor porque devuelve el resultado en cuanto encuentra la primera repetición, mientras que crear el conjunto completo siempre lee todos los valores.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def containsDuplicate(nums):
# Escribe el código aquíCaso 1
Caso 2
Caso 3
Entrada
nums = [3, 1, 4, 1, 5]
Esperado
true