目录

0744:寻找比目标字母大的最小字母

力扣第 744 题

题目

给你一个字符数组 letters,该数组按非递减顺序排序,以及一个字符 targetletters至少有两个不同的字符。

返回 letters 中大于 target 的最小的字符。如果不存在这样的字符,则返回 letters 的第一个字符。

示例 1:

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

示例 2:

输入: letters = ["c","f","j"], target = "c"
输出: "f"
解释:letters 中字典顺序上大于 'c' 的最小字符是 'f'。

示例 3:

输入: letters = ["x","x","y","y"], target = "z"
输出: "x"
解释:letters 中没有一个字符在字典上大于 'z',所以我们返回 letters[0]。

提示:

  • 2 <= letters.length <= 104
  • letters[i] 是一个小写字母
  • letters非递减顺序排序
  • letters 最少包含两个不同的字母
  • target 是一个小写字母

相似问题:

分析

#1

遍历找到第一个比 target 大的字母即可。如果都比 target 小,那么按照循环应该返回 letters[0]。

1
2
3
4
5
def nextGreatestLetter(self, letters: List[str], target: str) -> str:
	for letter in letters:
		if letter > target:
			return letter
	return letters[0]

124 ms

#2

也可以二分查找从最右边将 target 插入 nums 的位置 i。如果 i == len(letters),那么应该返回 letters[0]。

解答

1
2
def nextGreatestLetter(self, letters: List[str], target: str) -> str:
	return letters[bisect_right(letters, target) % (len(letters))]

124 ms