Single Number
Recibes una lista nums en la que cada valor aparece exactamente dos veces, excepto uno que aparece una sola vez. Devuelve el valor que aparece una sola vez.
Función
- numsinteger-array
- una lista en la que todos los valores aparecen dos veces, excepto uno
- Devuelveinteger
- el valor que aparece solo una vez
Restricciones
1 ≤ nums.length < 104-104 ≤ nums[i] ≤ 104- Cada valor aparece exactamente dos veces, excepto un valor que aparece exactamente una vez.
Ejemplos
- Entrada
- nums = [8, 3, 8]
- Salida
- 3
- Explicación
- El 8 aparece dos veces y el 3 aparece una vez, así que la respuesta es 3.
- Entrada
- nums = [5, -2, 7, 5, 7]
- Salida
- -2
- Explicación
- 5 y 7 aparecen dos veces cada uno, y -2 es el único valor que aparece una sola vez. Una respuesta negativa se encuentra de la misma manera que una positiva.
- Entrada
- nums = [42]
- Salida
- 42
- Explicación
- Una lista con un solo valor no tiene ningún par, así que ese valor es la respuesta.
+13 pruebas ocultas al enviar
Para ir más allá
¿Y si cada valor apareciera tres veces, excepto uno? XOR por sí solo ya no cancela los valores que aparecen tres veces. ¿Aún puedes encontrar el único valor en O(n) tiempo y con O(1) memoria adicional?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Si se pudiera hacer desaparecer cada par de valores iguales, solo quedaría la respuesta. ¿Existe una operación que convierta dos números iguales en nada?
XOR hace lo siguiente:
x ^ xes0yx ^ 0esx. Además, no depende del orden, así que las dos copias de un valor no tienen que estar una al lado de la otra para cancelarse.Mantén una variable que empiece en
0. Aplica XOR a cada valor denumsy después devuélvela. No se necesita ningún mapa ni ordenar.
Solución
Encontrar el único valor sin pareja es un problema de conteo, y un mapa hash cuenta cada valor en una sola pasada. El inconveniente es la memoria: un mapa crece con la lista. XOR elimina la necesidad de contar, porque aplicar XOR a un valor consigo mismo da 0. Aplica XOR a toda la lista y cada pareja se anula, dejando el único valor en una sola pasada con una variable.
Cuenta cada valor escaneando
Correcto, pero no termina con las pruebas más grandes
Intuición
Toma cada valor por turnos y recorre toda la lista para contar cuántas veces aparece. Un valor de un par cuenta como 2. El valor único cuenta como 1, así que devuelve el primer valor cuyo recuento es 1.
Esto es correcto porque los recuentos se deducen directamente de la definición de la respuesta y no requiere memoria adicional aparte de un contador.
Es lento porque cada uno de los n valores desencadena un recorrido completo de n valores. Cuando el valor único está al final de una lista de 9,999, eso se acerca a 10^8 comparaciones.
Algoritmo
- Recorre cada valor de
nums. - Recorre toda la lista y cuenta los valores iguales a él.
- Si el recuento es 1, devuelve ese valor.
def singleNumber(nums):
for value in nums:
# count() scans the whole list: O(n) per value.
if nums.count(value) == 1:
return value
return 0Cuenta con un mapa hash
Intuición
Volver a recorrer la lista para cada valor repite trabajo. Cuenta todos los valores en una sola pasada: un mapa hash de valores a recuentos, donde cada paso suma 1 al recuento del valor actual.
Para [5, -2, 7, 5, 7], el mapa queda como 5 → 2, -2 → 1, 7 → 2. Una segunda pasada por el mapa encuentra la entrada con recuento 1, que es -2.
Cada valor requiere una actualización del mapa, así que el tiempo es O(n). El mapa contiene aproximadamente n/2 entradas, lo que supone memoria adicional O(n). En C, que no tiene un mapa integrado, un arreglo de contadores indexado por value + 10^4 cumple la misma función porque los valores son pequeños.
Algoritmo
- Crea un mapa vacío de valores a recuentos.
- Para cada valor de
nums, suma 1 a su recuento. - Recorre el mapa y devuelve el valor cuyo recuento es 1.
def singleNumber(nums):
counts = {}
for value in nums:
counts[value] = counts.get(value, 0) + 1
for value, count in counts.items():
if count == 1:
return value
return 0XOR todos los valores
Intuición
XOR compara dos números bit a bit y establece un bit cuando son diferentes. De ello se deducen tres hechos: x ^ x = 0, x ^ 0 = x y el orden de las operaciones no importa.
Así que aplica XOR a toda la lista en una sola variable que comienza en 0. Puedes reagrupar las operaciones para que cada par se junte con su gemelo, y cada par se convierte en 0. Lo que queda es 0 ^ single, que es el valor único. Para [8, 3, 8]: 0 ^ 8 = 8, después 8 ^ 3 = 11, después 11 ^ 8 = 3.
Los números negativos también funcionan. XOR opera sobre los bits de la representación en complemento a dos, y dos números negativos iguales tienen los mismos bits, así que se cancelan como cualquier otro par. El bucle lee cada valor una vez y mantiene una variable: tiempo O(n) y memoria adicional O(1).
Algoritmo
- Establece
resulten 0. - Para cada valor de
nums, estableceresultenresult ^ value. - Devuelve
result.
def singleNumber(nums):
result = 0
for value in nums:
result ^= value
return result
Errores comunes y casos límite
El bucle XOR es corto, así que los errores se esconden en dónde empieza y en las alternativas que se suelen elegir.
- Empezar
resultennums[0]y después recorrer todos los valores, incluido el índice 0. El primer valor se aplica con XOR dos veces y se cancela. Empieza en 0 o sáltate el índice 0. - Ordenar y comparar elementos adyacentes de dos en dos, y luego olvidar que el valor único puede ser el último elemento. En
[1, 1, 2]no hay ningún par que no coincida, y la respuesta es el 2 que queda. - Usar
2 × sum(distinct values) - sum(nums). Da el número correcto, pero el conjunto de valores distintos requiereO(n)de memoria, algo que la versión con XOR evita. - Esperar que XOR funcione con otras cantidades de apariciones. Cancela los valores que aparecen un número par de veces. Si un valor apareciera tres veces, sobreviviría una copia y estropearía la respuesta.
Preguntas frecuentes4
¿Cuál es la complejidad temporal de Single Number?
La solución XOR se ejecuta en tiempo O(n) y usa O(1) espacio adicional, porque lee cada valor una vez y mantiene una variable. Un mapa hash también requiere tiempo O(n), pero necesita O(n) de memoria. Contar cada valor con un nuevo recorrido requiere O(n²).
¿Por qué XOR resuelve el problema del número único?
Aplicar XOR a un número consigo mismo da 0, aplicar XOR con 0 no cambia nada y el orden de las operaciones no importa. Así que, cuando aplicas XOR a toda la lista, puedes agrupar cada par y se anula hasta dar 0. Solo queda el valor que no tiene pareja.
¿Funciona el truco XOR con números negativos?
Sí. XOR opera sobre los bits que almacenan el número, y los números negativos se almacenan en complemento a dos. Dos números negativos iguales tienen bits idénticos, así que se cancelan exactamente igual que los positivos. En [5, -2, 7, 5, 7], el resultado es -2.
¿Cómo se resuelve cuando los otros valores aparecen tres veces?
XOR cancela pares, no tríos, así que falla en ese caso. En su lugar, cuenta cuántos valores tienen establecido cada uno de los 32 bits. Para cada bit, el recuento módulo 3 es el bit del único valor, porque los tríos suman múltiplos de 3. Esto sigue ejecutándose en tiempo O(n) con memoria extra O(1).
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def singleNumber(nums):
# Escribe el código aquíCaso 1
Caso 2
Caso 3
Entrada
nums = [8, 3, 8]
Esperado
3