LeetCode每日一题：寻找比目标字母大的最小字母（744题）

LeetCode每日一题：寻找比目标字母大的最小字母（744题）

题目描述

给定一个字符数组 letters，该数组按非递减顺序排序，以及一个字符 target。letters 里至少有两个不同的字符。返回 letters 中大于 target 的最小的字符。如果不存在这样的字符，则返回 letters 的第一个字符。

示例

示例 1：
输入: letters = ['c', 'f', 'j']，target = 'a'
输出: 'c'
解释：letters 中字典上比 'a' 大的最小字符是 'c'。

解题思路

由于 letters 是有序的，我们可以使用二分查找算法来高效地找到答案。二分查找可以帮助我们在 O(log n) 的时间复杂度内找到目标值。具体步骤如下：

1. 初始化两个指针 l 和 r，分别指向数组的开始和结束。
2. 当 l 小于 r 时，计算中间位置 mid。
3. 如果 letters[mid] 小于等于 target，则将 l 移动到 mid + 1，否则将 r 移动到 mid。
4. 最后，如果 letters[r] 大于 target，则返回 letters[r]，否则返回 letters[0]。

代码实现

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        // letters 有序，可以二分查找
        int l = 0, r = letters.size() - 1;
        while (l < r) {
            int mid = l + ((r - l) >> 1);
            if (letters[mid] <= target) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        if (letters[r] > target) {
            return letters[r];
        }
        return letters[0];
    }
};

总结

通过二分查找，我们可以高效地解决这个问题。这种方法不仅时间复杂度低，而且代码简洁易懂。在实际应用中，对于有序数据集，二分查找是一种非常有效的搜索方法。