题目:
给定一个只包含小写字母的有序数组letters
和一个目标字母 target
,寻找有序数组里面比目标字母大的最小字母。
数组里字母的顺序是循环的。举个例子,如果目标字母target = 'z'
并且有序数组为 letters = ['a', 'b']
,则答案返回 'a'
。
示例:
输入:letters = ["c", "f", "j"]target = "a"输出: "c"输入:letters = ["c", "f", "j"]target = "c"输出: "f"输入:letters = ["c", "f", "j"]target = "d"输出: "f"输入:letters = ["c", "f", "j"]target = "g"输出: "j"输入:letters = ["c", "f", "j"]target = "j"输出: "c"输入:letters = ["c", "f", "j"]target = "k"输出: "c"
注:
letters
长度范围在[2, 10000]
区间内。letters
仅由小写字母组成,最少包含两个不同的字母。- 目标字母
target
是一个小写字母。
解题思路:
如果letters.back()<=target,那么直接返回letters[0]即可;
剩余的情况,使用二分查找,进行查找。
代码:
class Solution {public: char nextGreatestLetter(vector& letters, char target) { if(target >= letters.back()) return letters[0]; int left=0,right=letters.size(); while(left
相关知识:
二分查找:
二分查找注意三个语句必须搭配
1.right = letters.size()。
2.left < right。
3.right = mid。
记住这一种即可。