Siguiente letra después del objetivo
La misión
Problema
Recibes una lista de letras minúsculas ordenada en orden no decreciente, que contiene al menos dos letras diferentes, y una letra objetivo. Devuelve la letra más pequeña de la lista que sea estrictamente mayor que el objetivo. Si ninguna letra es mayor, da la vuelta y devuelve la primera letra de la lista.
Ejemplos
Input: letters = ["c", "f", "j"], target = "a"
Output: "c"
Input: letters = ["c", "f", "f", "j"], target = "f"
Output: "j"
Por qué: estrictamente mayor significa que se saltan las dos copias de f
Input: letters = ["c", "f", "j"], target = "j"
Output: "c"
Por qué: caso límite: nada es mayor que j, así que la respuesta da la vuelta al inicio
Pistas
0 / 3
Un recorrido lineal funciona, pero la lista está ordenada. ¿Qué búsqueda clásica responde a la pregunta de dónde está la primera letra mayor que el objetivo?
Es una búsqueda de límite superior: encuentra el primer índice cuya letra sea estrictamente mayor que el objetivo. Todos los índices anteriores contienen una letra menor o igual que el objetivo.
Haz una búsqueda binaria con lo = 0 y hi = len(letters). Si la letra del medio es menor o igual que el objetivo, mueve lo más allá de ella; si no, mueve hi hasta ella. Cuando la búsqueda termine en lo, devuelve la letra en lo módulo la longitud, lo que cubre la vuelta al inicio.
- Tiempo objetivo
- O(log n)
- Espacio objetivo
- O(1)
Restricciones
- letters are lowercase and sorted non-decreasing
- at least two different letters
Solución
La primera letra estrictamente mayor que el objetivo es un límite superior, una de las búsquedas de frontera en las que el bucle mantiene un rango semiabierto y nunca devuelve un resultado antes de tiempo. Las letras menores o iguales que el objetivo empujan lo más allá del medio y las letras mayores bajan hi hasta él, así que cuando los dos se encuentran, lo es el primer índice que contiene una letra mayor. Si todas las letras son menores o iguales que el objetivo, lo termina en la longitud de la lista, y tomar ese valor módulo la longitud lo convierte en la vuelta al inicio. El tiempo es O(log n) y el espacio es 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")) # -> c¿Lo que te frena es la idea y no el código? Variantes de la búsqueda binaria lo explica.