Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一个字符组成的已从小到大排序的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]

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理