Próxima letra depois do alvo
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
Uma varredura linear funciona, mas a lista está ordenada. Qual busca clássica responde onde fica a primeira letra maior que o alvo?
Esta é uma busca de limite superior (upper bound): encontre o primeiro índice cuja letra é estritamente maior que o alvo. Todo índice antes dele guarda uma letra menor ou igual ao alvo.
Faça a busca binária com lo = 0 e hi = len(letters). Se a letra do meio for menor ou igual ao alvo, mova lo para depois dela; caso contrário, mova hi para ela. Quando a busca terminar em lo, retorne a letra em lo módulo o tamanho, o que cobre a volta.
- Tempo-alvo
- O(log n)
- Espaço-alvo
- O(1)
Restrições
- letters are lowercase and sorted non-decreasing
- at least two different letters
Solução
A primeira letra estritamente maior que o alvo é um limite superior, uma das buscas de fronteira em que o loop mantém um intervalo semiaberto e nunca retorna antes do fim. Letras menores ou iguais ao alvo empurram lo para depois do meio, e letras maiores puxam hi até ele; assim, quando os dois se encontram, lo é o primeiro índice com uma letra maior. Se todas as letras forem menores ou iguais ao alvo, lo termina no tamanho da lista, e aplicar o módulo pelo tamanho transforma isso na volta ao início. O tempo é O(log n) e o espaço é O(1).
def next_letter(letters, target):
lo, hi = 0, len(letters)
while lo < hi: # find the first letter greater than target
mid = (lo + hi) // 2
if letters[mid] <= target:
lo = mid + 1
else:
hi = mid
return letters[lo % len(letters)] # past the end wraps to the front
print(next_letter(["c", "f", "j"], "a")) # -> c
print(next_letter(["c", "f", "f", "j"], "f")) # -> j
print(next_letter(["c", "f", "j"], "j")) # -> cTravou na ideia, e não no código? Variações da busca binária explica isso.