Tutorial para resolver problemas de números faltantes: una comparación completa de 3 soluciones | Mejores prácticas de LeetCode 268

Tutorial para resolver problemas de números faltantes (ilustrado) | LeetCode 268

Este artículo ofrece un análisis completo de la solución al problema LeetCode 268 "Número faltante": desde el enfoque de resolución de problemas y los pasos del algoritmo hasta la complejidad temporal y espacial. Además, resume los casos límite y compara tres soluciones, lo que le ayudará a comprender "Número faltante" desde cero.

Explore diversas soluciones LeetCode en Python, C++, JavaScript, SQL y TypeScript. Ideal para preparación de entrevistas, aprendizaje y práctica de código en múltiples lenguajes de programación. Enlace de repositorio de Github


Dada una matriz números que contiene norte números distintos en el rango [0,n], devolver el único número en el rango que falta en la matriz.

 

Ejemplo 1:

Aporte: números = [3,0,1]
Producción: 2
Explicación: n = 3 ya que hay 3 números, por lo que todos los números están en el rango [0,3]. 2 es el número que falta en el rango ya que no aparece en números.

Ejemplo 2:

Aporte: números = [0,1]
Producción: 2
Explicación: n = 2 ya que hay 2 números, por lo que todos los números están en el rango [0,2] es el número que falta en el rango ya que no aparece en números.

Ejemplo 3:

Aporte: números = [9,6,4,2,3,5,7,0,1]
Producción: 8
Explicación: n = 9 ya que hay 9 números, por lo que todos los números están en el rango [0,9] es el número que falta en el rango ya que no aparece en números.

 

Restricciones:

  • n == números.longitud
  • 1 <= norte <= 10 4
  • 0 <= números[i] <= n
  • todos los numeros de números son único.

 

Hacer un seguimiento: ¿Podrías implementar una solución usando solo O(1) complejidad espacial adicional y En) ¿Complejidad del tiempo de ejecución?

Pitón

				
					Complejidad de tiempo de #: O(n) Complejidad de espacio de #: O(1) al escribir import List clase Solución: def MissingNumber(self, nums: List[int]) -> int: numSet = set(nums) for i in range( len(numSet) + 1): si no estoy en numSet: devuelve i nums = [9, 6, 4, 2, 3, 5, 7, 0, 1] print(Solution().missingNumber(nums))
				
			

Ejercicios de extensión de problemas de LeetCode

Se recomienda practicar con otras notas de resolución de problemas de la misma serie:

Enfoque para la resolución de problemas con números faltantes

Hay n+1 números del 0 al n a los que les falta uno. Existen dos soluciones elegantes: una consiste en usar la fórmula de suma gaussiana para calcular la suma que debería tener y luego restar la suma real; la otra consiste en usar la operación XOR (XOR del 0 al n con todos los números del arreglo), de modo que los pares se cancelen entre sí, dejando el valor faltante. La versión XOR no produce desbordamiento y es más segura.

Pasos del algoritmo para números faltantes

  1. Inicializar resultado = n (rellenar el número al que no se puede acceder mediante el índice).
  2. Visite el array con índice i y valor nums[i].
  3. Sea resultado = resultado XOR i XOR nums[i].
  4. Una vez finalizado el proceso, el resultado será el número que falta.

Análisis de complejidad de números faltantes

proyectoComplejidad
complejidad temporalEn)
Complejidad espacialO(1)

Un único escaneo lineal, con dos operaciones XOR por paso, tiene una complejidad temporal de O(n). Utiliza solo una variable y tiene una complejidad espacial de O(1). En comparación con el método de suma, XOR no presenta ningún riesgo de desbordamiento.

Casos límite y errores comunes de números faltantes

  • El valor que falta podría ser 0 o n, y ambos extremos deben poder manejarlo correctamente.
  • El método de sumatoria puede desbordarse cuando n es muy grande, mientras que el método XOR no presenta este problema.
  • Se garantiza que el arreglo no contiene elementos repetidos y que todos sus elementos están en el rango de 0 a n; de lo contrario, ambas soluciones fallarán.
  • También es posible encontrar puntos de interrupción después de la ordenación, pero requiere un tiempo adicional de O(n log n).

Comparación de otras soluciones para el problema de números faltantes

solucióntiempoespacioilustrar
Después de ordenar, escanee para encontrar puntos de interrupción.O(n iniciar sesión n)O(1)Correcto, pero lento.
Utilice un juego para registrar los números que han aparecido.En)En)Pasa más espacio
Cancelación XOREn)O(1)Este artículo adopta