Pular para o conteúdo

Próxima letra depois do alvo

Fácil#binary-search#upper-bound~15 min

A missão

Problema

Você recebe uma lista de letras minúsculas ordenada em ordem não decrescente, com pelo menos duas letras diferentes, e uma letra alvo. Retorne a menor letra da lista que seja estritamente maior que o alvo. Se nenhuma letra for maior, dê a volta e retorne a primeira letra da lista.

Exemplos

Input:  letters = ["c", "f", "j"], target = "a"
Output: "c"
Input:  letters = ["c", "f", "f", "j"], target = "f"
Output: "j"
Por quê: estritamente maior significa que as duas cópias de f são puladas
Input:  letters = ["c", "f", "j"], target = "j"
Output: "c"
Por quê: edge case: nada é maior que j, então a resposta dá a volta até o início

Dicas

0 / 3

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

Restrições

  • letters are lowercase and sorted non-decreasing
  • at least two different letters

Travou na ideia, e não no código? Variações da busca binária explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado