小旭讲解 LeetCode 744. 寻找比目标字母大的最小字母

题目

 LeetCode 744. 寻找比目标字母大的最小字母

思路 – 二分搜索（经典模板）

该题的数据范围，可以朴素查找。

可以借用此题，锻炼下二分搜索。既然谈到一个区间，且具有顺序，那么不妨使用二分搜索。

根据题意，我们需要在非严格单调递增的区间中，从左向右，找到第一个大目标值的值。如果没有即返回第一个元素（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/