题目:
744.寻找比目标字母大的最小字母(Easy)
代码:
一开始用纯左闭右开二分,忽略两种情况:
1.遗漏均不满足,返回Leeters[0],已提前加判断;
2.由于左闭右开适用于判断,等于此处的位置,因此若存在相同的,此方法返回的是相等位置;而本题希望返回比相等更大一个元素,因此在左闭右开基础上,把letters[mid] = target也归到需要向右搜索即可。
python">class Solution:
def nextGreatestLetter(self, letters: List[str], target: str) -> str:
# 二分法,左闭右开,结果不对;
# 看了下出差原因,是因为当有相同时候,返回的值小一位;
# 因此采用左闭,右闭
# 妄自揣测下:字符的ASCII码 不同导致可以直接对字符进行比较;
left , right = 0 , len(letters)
if target >= letters[-1]: # 如果大于Letters最后一个元素直接返回Letters[0]
return letters[0]
while left < right:
mid = left + (right-left)//2
if letters[mid] <= target : # 往右搜索,左闭右开
left = mid + 1
else :
right = mid
# 一开始默写纯左闭右开,发现:1.遗漏均不满足,返回Leeters[0],已提前加判断;
# 2.由于左闭右开适用于判断,等于此处的位置,因此若存在相同的,此方法返回的是相等位置;
# 而本题希望返回比相等更大一个元素,因此在左闭右开基础上,把letters[mid] = target也归到需要向右搜索即可。
return letters[left]