小旭讲解 LeetCode 744. 寻找比目标字母大的最小字母
小旭讲解 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/
0 0 vote
Article Rating
Subscribe
提醒
guest
4 评论
Newest
Oldest Most Voted
Inline Feedbacks
View all comments
容添下

麻雀虽小五脏俱全

站元素主机

感谢分享 赞一个

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

[…] [1]. 小旭讲解 LeetCode 744. 寻找比目标字母大的最小字母. https://qoogle.top/xiaoxu-tutorial-leetcode-744-find-smallest-letter-greater-than-target/ […]