K-ésimo número que falta en una lista
La misión
Problema
Los números de ticket se reparten desde 1 en adelante, y nums lista los que ya se usaron, en orden estrictamente creciente y todos positivos. Devuelve el k-ésimo número positivo más pequeño que no aparece en nums, donde k es al menos 1. Apunta a una solución más rápida que recorrer los números uno por uno.
Ejemplos
Input: nums = [2, 3, 4, 7, 11], k = 5
Output: 9
Por qué: los números que faltan son 1, 5, 6, 8, 9, 10, ...
Input: nums = [1, 2, 3, 4], k = 2
Output: 6
Por qué: no falta nada dentro de la lista, así que la respuesta está más allá de su final
Input: nums = [], k = 4
Output: 4
Por qué: caso límite: si no se usó ninguno, el k-ésimo número que falta es el propio k
Pistas
0 / 3
Si no faltara nada, el valor en el índice i sería i + 1. La diferencia entre el valor real e i + 1 te dice algo útil.
nums[i] menos (i + 1) es la cantidad de valores que faltan por debajo de nums[i], y nunca disminuye a medida que i crece, así que se puede buscar con búsqueda binaria.
Encuentra el primer índice donde esa cantidad llega a k. Si ese índice es lo, exactamente lo valores de la lista están por debajo de la respuesta, así que la respuesta es lo + k.
- Tiempo objetivo
- O(log n)
- Espacio objetivo
- O(1)
Restricciones
- nums is strictly increasing
- every value in nums is positive
- k ≥ 1
Solución
En el índice i la lista ya usó i + 1 números, así que faltan nums[i] menos (i + 1) números por debajo de nums[i], y esa cantidad nunca disminuye a lo largo de la lista. La búsqueda binaria encuentra lo, el primer índice donde faltan al menos k números, o la longitud de la lista si no hay ninguno. Entonces la respuesta queda después de exactamente lo números usados y es el k-ésimo número que no está entre ellos, es decir, lo + k. El tiempo es O(log n) y el espacio es O(1).
def kth_missing(nums, k):
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] - (mid + 1) < k: # fewer than k missing below nums[mid]
lo = mid + 1
else:
hi = mid
return lo + k # lo used numbers lie below the answer
print(kth_missing([2, 3, 4, 7, 11], 5)) # -> 9
print(kth_missing([1, 2, 3, 4], 2)) # -> 6
print(kth_missing([], 4)) # -> 4
print(kth_missing([5, 6, 7], 3)) # -> 3¿Lo que te frena es la idea y no el código? Búsqueda binaria lo explica.