给出一个字符组成的已从小到大排序的list和一个target字符,问list中第一个比target大的字符是什么,若不存在,输出list第一个字符,二分的简单应用
手写二分:
1 #744
2 #Runtime: 83 ms (Beats 49.15%)
3 #Memory: 15.2 MB (Beats 72.73%)
4
5 class Solution(object):
6 def nextGreatestLetter(self, letters, target):
7 """
8 :type letters: List[str]
9 :type target: str
10 :rtype: str
11 """
12 def b_search(ch):
13 l = 0
14 r = len(letters) - 1
15 while l < r:
16 mid = (l + r) // 2
17 if letters[mid] <= target:
18 l = mid + 1
19 else:
20 r = mid
21 return l
22 idx = b_search(target)
23
24 if letters[idx] > target:
25 return letters[idx]
26 return letters[0]
用python自带二分函数;
1 #744
2 #Runtime: 80 ms (Beats 66.76%)
3 #Memory: 15.2 MB (Beats 93.75%)
4
5 class Solution(object):
6 def nextGreatestLetter(self, letters, target):
7 """
8 :type letters: List[str]
9 :type target: str
10 :rtype: str
11 """
12 idx = bisect.bisect_right(letters, target)
13
14 if idx < len(letters):
15 return letters[idx]
16 return letters[0]