K-ésimo número que falta na lista
A missão
Problema
Números de ingresso são distribuídos a partir de 1, e nums lista os que já foram usados, em ordem estritamente crescente e todos positivos. Retorne o k-ésimo menor número positivo que não aparece em nums, em que k é pelo menos 1. Busque uma solução mais rápida do que percorrer os números um por um.
Exemplos
Input: nums = [2, 3, 4, 7, 11], k = 5
Output: 9
Por quê: os números que faltam são 1, 5, 6, 8, 9, 10, ...
Input: nums = [1, 2, 3, 4], k = 2
Output: 6
Por quê: não falta nada dentro da lista, então a resposta fica depois do fim dela
Input: nums = [], k = 4
Output: 4
Por quê: edge case: sem nenhum número usado, o k-ésimo número que falta é o próprio k
Dicas
0 / 3
Se não faltasse nada, o valor no índice i seria i + 1. A diferença entre o valor real e i + 1 diz algo útil.
nums[i] menos (i + 1) é a quantidade de valores que faltam abaixo de nums[i], e ela nunca diminui conforme i cresce; por isso, dá para aplicar busca binária sobre ela.
Encontre o primeiro índice em que essa contagem chega a k. Se esse índice for lo, exatamente lo valores da lista ficam abaixo da resposta, então a resposta é lo + k.
- Tempo-alvo
- O(log n)
- Espaço-alvo
- O(1)
Restrições
- nums is strictly increasing
- every value in nums is positive
- k ≥ 1
Solução
No índice i, a lista já usou i + 1 números, então faltam nums[i] menos (i + 1) números abaixo de nums[i], e essa contagem nunca diminui ao longo da lista. A busca binária encontra lo, o primeiro índice em que faltam pelo menos k números, ou o tamanho da lista, se esse índice não existir. A resposta, então, fica depois de exatamente lo números usados e é o k-ésimo número que não está entre eles, ou seja, lo + k. O tempo é O(log n) e o espaço é 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)) # -> 3Travou na ideia, e não no código? Busca binária explica isso.