744. 寻找比目标字母大的最小字母-蒲公英云

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

给你一个排序后的字符列表 l e t t e r s letters letters ，列表中只包含小写英文字母。另给出一个目标字母 t a r g e t target target，请你寻找在这一有序列表里比目标字母大的最小字母。

在比较时，字母是依序循环出现的。举个例子：

如果目标字母 t a r g e t = ′ z ′ target = ‘z’ target=′z′ 并且字符列表为 l e t t e r s = [ ′ a ′ , ′ b ′ ] letters = [‘a’, ‘b’] letters=[′a′,′b′]，则答案返回 ′ a ′ ‘a’ ′a′

示例 1：

输入: letters = [“c”, “f”, “j”]，target = “a”
输出: “c”

示例 2:

输入: letters = [“c”,“f”,“j”], target = “c”
输出: “f”

示例 3:

输入: letters = [“c”,“f”,“j”], target = “d”
输出: “f”

提示：

2 < = l e t t e r s . l e n g t h < = 1 0 4 2 <= letters.length <= 10^4 2<=letters.length<=104
l e t t e r s [ i ] letters[i] letters[i] 是一个小写字母
l e t t e r s letters letters 按非递减顺序排序
l e t t e r s letters letters 最少包含两个不同的字母
t a r g e t target target 是一个小写字母

思路：二分查找

利用列表有序的特点，可以使用二分查找降低时间复杂度。
首先比较目标字母和列表中的最后一个字母，当目标字母大于或等于列表中的最后一个字母时，答案是列表的首个字母。当目标字母小于列表中的最后一个字母时，列表中一定存在比目标字母大的字母，可以使用二分查找得到比目标字母大的最小字母。
初始时，二分查找的范围是整个列表的下标范围。每次比较当前下标处的字母和目标字母，如果当前下标处的字母大于目标字母，则在当前下标以及当前下标的左侧继续查找，否则在当前下标的右侧继续查找。

代码：

public class min_letter {
    public static void main(String[] args) {
        // TODO 自动生成的方法存根
        char [] letters = {
    'c', 'f', 'j'};
        char target = 'k';
        System.out.println(nextGreatestLetter(letters, target));
    }
    public static char nextGreatestLetter(char[] letters, char target) {
        int l = 0, h = letters.length - 1;
        if(target >= letters[h])
            return letters[0];
        int t = (target - 'a' + 1) % 26;
        while(l < h) {
            int m = l + (h - l)/2;
            if((letters[m] - 'a' + 1) <= t) {
                l = m + 1;
            }else{
                h = m;
            }
        }
        return letters[l];
    }
}

复杂度分析：

时间复杂度： O ( l o g ⁡ n ) O(log⁡n) O(log⁡n)，其中 n n n 是列表 l e t t e r s letters letters 的长度。二分查找的时间复杂度是 O ( l o g ⁡ n ) O(log⁡n) O(log⁡n)。
空间复杂度： O ( 1 ) O(1) O(1)