[Leetcode][python]Find Smallest Letter Greater Than Target/寻找比目标字母大的最小字母

「爱情、让人受尽委屈。」 2022-05-26 12:53 234阅读 0赞

题目大意

给定一个有序的字符数组 letters 和一个字符 target，要求找出 letters 中大于 target 的最小字符。letters 字符数组是循环数组。

解题思路

二分查找变种：
应该注意最后返回的是 l 位置的字符。

代码

  1. class Solution(object):
  2.     def nextGreatestLetter(self, letters, target):
  3.         """
  4.         :type letters: List[str]
  5.         :type target: str
  6.         :rtype: str
  7.         """
  8.         l = 0
  9.         r = len(letters) - 1
  10.         while l <= r:
  11.             m = l + (r - l) / 2
  12.             if letters[m] <= target:
  13.                 l = m + 1
  14.             else:
  15.                 r = m - 1
  16.         if l < len(letters):
  17.             return letters[l]
  18.         else:
  19.             return letters[0]

总结

发表评论

表情：
评论列表 （有 0 条评论，234人围观）

还没有评论，来说两句吧...

相关阅读