Pular para o conteúdo

K-ésimo número que falta na lista

Fácil#binary-search#counting~20 min

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

Tempo-alvo
O(log n)
Espaço-alvo
O(1)

Restrições

  • nums is strictly increasing
  • every value in nums is positive
  • k ≥ 1

Travou na ideia, e não no código? Busca binária explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado