网站开发框架技术,ui设计主要是做什么,免费搭建服务器,上海58同城招聘网最新招聘本题是二分查找板块中的一个简单题目#xff0c;不过二分查找比较注重于细节。所以我会着重点出来。
思考#xff1a;从查找字母这一个要求来说#xff0c;我们要么选择遍历#xff0c;要么选择二分查找#xff0c;因为这里是非递减的#xff0c;那么我们自然的就会想到…本题是二分查找板块中的一个简单题目不过二分查找比较注重于细节。所以我会着重点出来。
思考从查找字母这一个要求来说我们要么选择遍历要么选择二分查找因为这里是非递减的那么我们自然的就会想到用二分查找的方法去查找所以就忽略遍历这一个比较笨的法子。
那么我们需要找的并不是数组中对应的字符而是比目标字符大一点的第一个最小字母。这里就说明了我们的判断条件并不简单的就是三个if else 了而是判断区间。
那么就开始来从题目中判断条件。我们看到它说的是第一个大于它的字母那么这个判定条件就应该满足letters[mid]target这样才行并不是letters[mid]target请读者细细品味这一点。
然后在循环结束之后我们就开始进行判断当前指向的字母是否是我们需要的字母这里还需要再次判断正确性如果是那么就直接返回这个字母不是的话那么按照题目要求我们需要返回letters[0]。
注意在最后判断的时候如果说当前的字母是与目标字母相同的情况我们也是返回letters[0]因为题目中要求的是大于它的字母并不包括等于这个条件的字母。
class Solution {
public:char nextGreatestLetter(vectorchar letters, char target) {int left0;int rightletters.size()-1;while(leftright){int mid(rightleft)/2;if(letters[mid]target)rightmid;elseleftmid1;}if(letters[right]target)return letters[0];else return letters[right];}
};