0744. 寻找比目标字母大的最小字母

0744. 寻找比目标字母大的最小字母 #

  • 标签:二分查找
  • 难度:简单

题目大意 #

给定一个排序后的字符列表 letters,列表中只包含小写英文字母。再给定一个目标字符 target。从列表中找出比 target 更大的最小字母。

  • 假设字母是依次循环的,比如:…、x、y、z、a、b、…

解题思路 #

利用二分查找,找到比 target 大的字母。注意 target 可能大于 letters 的所有字符,此时应返回 letters 的第一个字母。

我们可以假定 target 的取值范围为 [0, len(letters)]。当 target 取到 len(letters) 时,说明 target 大于 letters 的所有字符,对 len(letters) 取余即可得到 letters[0]。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        n = len(letters)
        left = 0
        right = n
        while left < right:
            mid = left + (right - left) // 2
            if letters[mid] <= target:
                left = mid + 1
            else:
                right = mid
        return letters[left % n]
本站总访问量  次  |  您是本站第  位访问者