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.longitud1 <= norte <= 10 40 <= números[i] <= n- todos los numeros de
númerosson ú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
- Inicializar resultado = n (rellenar el número al que no se puede acceder mediante el índice).
- Visite el array con índice i y valor nums[i].
- Sea resultado = resultado XOR i XOR nums[i].
- Una vez finalizado el proceso, el resultado será el número que falta.
Análisis de complejidad de números faltantes
| proyecto | Complejidad |
|---|---|
| complejidad temporal | En) |
| Complejidad espacial | O(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ón | tiempo | espacio | ilustrar |
|---|---|---|---|
| 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 XOR | En) | O(1) | Este artículo adopta |
