题目
思路 – 二分搜索(经典模板)
该题的数据范围,可以朴素查找。
可以借用此题,锻炼下二分搜索。既然谈到一个区间,且具有顺序,那么不妨使用二分搜索。
根据题意,我们需要在非严格单调递增的区间中,从左向右,找到第一个大目标值的值。如果没有即返回第一个元素(letters[0])。
如何写一个二分?
每次写二分时,都会为边界条件抓狂,那么这次我们来看看如何写这个二分。
class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
int l=0,h=letters.size()-1,m;
while(l<h) {
m=l+h>>1;
if (letters[m]>target) {
h=m;
} else {
l=m+1;
}
}
if (letters[l] <= target) return letters[0];
return letters[l];
}
};
上面代码中,查找的是第一个大于目标值的值。可以这样理解,在非严格单调递增的区间查找时,当中值(letters[m])> 目标值(target)时,此时取左区间,且当前中值有可能是我们要查找的值,所以左区间的右边界能够取到 m 的位置,故 h=m;否则,l = m + 1。
那么,还有一个问题,如何防止 while 死循环,如果观察是h = m; l = m + 1的模式,那么需要将中值的索引,进行“向下取整”,即m=l+h>>1;因为,向下取整才能正确地让 m 逼近并且等于 l,以至于最终 h 与 l 逼近到一个位置上。同理,若观察室 l = m; h = m – 1 的模式,那么中值则“向上取整”,即m=l+h+1>>1;
通过上面取中值的方式,我们可以发现,其实二分的过程是一个不断逼近区间,直到长度为 1 的过程。
如何查找不同的值?
那么,如何:
- 在非严格单调递增区间查找第一个 >= 目标值的值
- 在非严格单调递增区间查找第一个 < 目标值的值
- 在非严格单调递增区间查找第一个 <= 目标值的值
这些问题,都可以通过调整中值与目标值的判断关系,来解决。大家可以尝试一下。
比如,如何找到“非严格单调递增区间查找第一个 >= 目标值的值”,代码如下:
class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
int l=0,h=letters.size()-1,m;
while(l<h) {
m=l+h>>1;
if (letters[m]>=target) {
h=m;
} else {
l=m+1;
}
}
if (letters[l] < target) return letters[0];
return letters[l];
}
};
那么,相信通过上面的思考,大家能够对二分搜索有一个比较清晰的认知了。
c++ 中的 lower_bound 和 upper_bound 如何理解?
- lower_bound 在非严格单调递增区间,从左向右找到,第一个大于等于目标值的值的索引
- upper_bound 在非严格单调递增区间,从左向右找到,第一个大于目标值的值的索引
#include <vector>
#include <iostream>
using namespace std;
int main()
{
// 0 1 2 3 4 5 6 7 8 9 10 11 12
vector<int> a{1,2,3,3,3,4,4,4,4,5,5, 6, 7};
cout<<lower_bound(a.begin(), a.end(), 3) - a.begin()<<endl;
cout<<upper_bound(a.begin(), a.end(), 3) - a.begin()<<endl;
return 0;
}
代码
见上述第代码片段
复杂度分析
Time: O(log n)
Space: O(1)
欢迎分享,引用。若转载,请联系我,谢谢配合。 本文地址:https://qoogle.top/xiaoxu-tutorial-leetcode-744-find-smallest-letter-greater-than-target/
1undersigned
麻雀虽小五脏俱全
感谢分享 赞一个
[…] 小旭讲解 LeetCode 744. 寻找比目标字母大的最小字母 […]
[…] [1]. 小旭讲解 LeetCode 744. 寻找比目标字母大的最小字母. https://qoogle.top/xiaoxu-tutorial-leetcode-744-find-smallest-letter-greater-than-target/ […]