Giả sử ta có một danh sách các ký tự đã sắp xếp letters. Danh sách này chỉ chứa chữ cái thường, bây giờ ta có một ký tự mục tiêu t, ta cần tìm phần tử nhỏ nhất trong danh sách lớn hơn mục tiêu cho trước.
Và letters cũng quay vòng. Vì vậy, nếu mục tiêu là t = 'z' và letters = ['a', 'b'], câu trả lời là 'a'.
Ví dụ, nếu đầu vào là ["c", "f", "j"], t = 'a', thì đầu ra sẽ là 'c'.
Để giải quyết, ta thực hiện các bước sau:
- l := 0
- r := kích thước letters - 1
- Khi l <= r, thực hiện:
- mid := (l + r) / 2 lấy phần nguyên
- Nếu letters[mid] > target, thì:
- r := mid - 1
- Ngược lại:
- l := mid + 1
- Trả về letters[l modulo kích thước letters]
Hãy xem triển khai sau để hiểu rõ hơn:
Ví dụ
class Solution: def nextGreatestLetter(self, letters, target): l = 0 r = len(letters) - 1 while l <= r: mid = (l + r)//2 if letters[mid] > target: r = mid - 1 else: l = mid + 1 return letters[l % len(letters)] ob = Solution() print(ob.nextGreatestLetter(["c", "f", "j"], "a"))
Đầu vào
["c", "f", "j"], "a"
Đầu ra
c