ค้นหาตัวอักษรที่เล็กที่สุดที่มากกว่าเป้าหมายใน Python

สมมติว่าเรามีรายชื่อตัวอักษรที่เรียงลำดับแล้ว มีเฉพาะตัวอักษรพิมพ์เล็ก ตอนนี้เรามีตัวอักษรเป้าหมาย t เราต้องหาองค์ประกอบที่เล็กที่สุดในรายการที่ใหญ่กว่าเป้าหมายที่กำหนด

และตัวอักษรก็พันรอบ ดังนั้น หากเป้าหมายคือ t ='z' และตัวอักษร =['a', 'b'] คำตอบคือ 'a'

ดังนั้น หากอินพุตเป็น ["c", "f", "j"], t ='a' ผลลัพธ์จะเป็น 'c'

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• l :=0
• r :=ขนาดของตัวอักษร - 1
• ในขณะที่ l <=r ทำ
  • กลาง :=(l + r) / 2 เป็นจำนวนเต็ม
  • ถ้าตัวอักษร[กลาง]> เป้าหมาย แล้ว
    • r :=กลาง -1
  • มิฉะนั้น
    • l :=กลาง + 1
• ส่งคืนตัวอักษร[l ขนาด mod ของตัวอักษร]

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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"))

อินพุต

["c", "f", "j"], "a"

ผลลัพธ์

c