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

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

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

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

如果目标字母$target{=}^{\prime }{z}^{\prime }$ 并且字符列表为 $letters={[}^{\prime }{a}^{\prime }{,}^{\prime }{b}^{\prime }]$，则答案返回 ${}^{\prime }{a}^{\prime }$

示例 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<=letters.length<=10^4$
$letters[i]$ 是一个小写字母
$letters$ 按非递减顺序排序
$letters$ 最少包含两个不同的字母
$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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

复杂度分析：

• 时间复杂度：$O(logn)$，其中 $n$ 是列表 $letters$ 的长度。二分查找的时间复杂度是 $O(logn)$。
• 空间复杂度：$O(1)$

注：仅供学习参考

来源：力扣