Hedeften sonraki harf
Görev tanımı
Problem
Sana azalmayan sırada sıralı, en az iki farklı harf içeren küçük harflerden oluşan bir liste ve bir hedef harf veriliyor. Listedeki hedeften büyük (eşit değil) en küçük harfi döndür. Hiçbir harf büyük değilse başa sar ve listenin ilk harfini döndür.
Örnekler
Input: letters = ["c", "f", "j"], target = "a"
Output: "c"
Input: letters = ["c", "f", "f", "j"], target = "f"
Output: "j"
Neden: harf büyük olmalı, eşit yetmez; bu yüzden f'nin iki kopyası da atlanır
Input: letters = ["c", "f", "j"], target = "j"
Output: "c"
Neden: edge case: hiçbir şey j'den büyük değil, cevap başa sarar
İpuçları
0 / 3
Doğrusal bir tarama işe yarar ama liste sıralı. Hedeften büyük ilk harfin nerede durduğu sorusunu hangi klasik arama cevaplar?
Bu bir üst sınır araması: harfi hedeften büyük olan ilk indeksi bul. Ondan önceki her indeks hedeften küçük ya da ona eşit bir harf tutar.
lo = 0 ve hi = len(letters) ile ikili arama yap. Ortadaki harf hedeften küçük ya da ona eşitse lo'yu ötesine taşı, değilse hi'yi ona taşı. Arama lo'da bitince lo'daki harfi uzunluğa göre mod alarak döndür; bu, sarmayı da kapsar.
- Hedef zaman
- O(log n)
- Hedef alan
- O(1)
Kısıtlar
- letters are lowercase and sorted non-decreasing
- at least two different letters
Çözüm
Hedeften büyük ilk harf bir üst sınırdır; döngünün yarı açık bir aralık tuttuğu ve asla erken dönmediği sınır aramalarından biri. Hedeften küçük ya da ona eşit harfler lo'yu ortanın ötesine iter, büyük harfler hi'yi ona çeker; böylece ikisi buluştuğunda lo büyük bir harf tutan ilk indekstir. Her harf hedeften küçük ya da ona eşitse lo listenin uzunluğunda biter ve onu uzunluğa göre mod almak bunu başa sarmaya çevirir. Zaman O(log n), alan 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")) # -> cKodda değil de fikirde mi takıldın? İkili arama varyantları bunu anlatıyor.