Tìm chữ cái nhỏ nhất lớn hơn mục tiêu trong Python

Giả sử chúng ta có một danh sách các ký tự được sắp xếp. Phần tử này chỉ chứa các chữ cái thường, bây giờ chúng ta có một chữ cái đích là t, chúng ta phải tìm phần tử nhỏ nhất trong danh sách mà lớn hơn mục tiêu đã cho.

Và các chữ cái cũng quấn quanh. Vì vậy, nếu mục tiêu là t ='z' và các chữ cái =['a', 'b'], thì câu trả lời là 'a'.

Vì vậy, nếu đầu vào là ["c", "f", "j"], t ='a', thì đầu ra sẽ là 'c'.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• l:=0
• r:=kích thước của các chữ cái - 1
• trong khi l <=r, thực hiện
  • mid:=(l + r) / 2 dưới dạng số nguyên
  • if các chữ cái [mid]> target, then
    • r:=mid -1
  • nếu không,
    • l:=mid + 1
• trả về các chữ cái [l kích thước sửa đổi của các chữ cái]

Hãy cùng chúng tôi xem cách 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