744. 寻找比目标字母大的最小字母
744. 寻找比目标字母大的最小字母
题目
You are given an array of characters letters
that is sorted in non- decreasing order , and a character target
. There are at least two different characters in letters
.
Return the smallest character inletters
that is lexicographically greater thantarget
. If such a character does not exist, return the first character in letters
.
Example 1:
Input: letters = ["c","f","j"], target = "a"
Output: "c"
Explanation: The smallest character that is lexicographically greater than 'a' in letters is 'c'.
Example 2:
Input: letters = ["c","f","j"], target = "c"
Output: "f"
Explanation: The smallest character that is lexicographically greater than 'c' in letters is 'f'.
Example 3:
Input: letters = ["x","x","y","y"], target = "z"
Output: "x"
Explanation: There are no characters in letters that is lexicographically greater than 'z' so we return letters[0].
Constraints:
2 <= letters.length <= 10^4
letters[i]
is a lowercase English letter.letters
is sorted in non-decreasing order.letters
contains at least two different characters.target
is a lowercase English letter.
题目大意
给你一个字符数组 letters
,该数组按非递减顺序 排序,以及一个字符 target
。letters
里至少有两个不同 的字符。
返回 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 <= 10^4
letters[i]
是一个小写字母letters
按非递减顺序 排序letters
最少包含两个不同的字母target
是一个小写字母
解题思路
这是一道典型的查找问题,letters
是按照字典序排序的,因此可以利用二分查找的思想高效解决,目标是找到第一个大于 target
的字符,如果 target
大于等于 letters
的所有元素,则答案是 letters[0]
。
- 初始化左右指针:
- 左指针
left = 0
,右指针right = letters.length - 1
。
- 左指针
- 二分查找:
- 计算中间点
mid = (left + right) / 2 | 0
。 - 如果
letters[mid] > target
,更新右边界为mid - 1
。 - 如果
letters[mid] <= target
,更新左边界为mid + 1
。
- 计算中间点
- 结束条件:
- 当
left == right
时,检查对应位置的字符。 - 如果
left
超过数组范围(即letters[left]
不存在),返回letters[0]
。
- 当
- 返回结果:
- 返回大于
target
的最小字符。
- 返回大于
复杂度分析
- 时间复杂度:
O(log n)
,其中n
是数组的长度,二分查找的时间复杂度为O(log n)
。 - 空间复杂度:
O(1)
,仅使用了常数空间。
代码
/**
* @param {character[]} letters
* @param {character} target
* @return {character}
*/
var nextGreatestLetter = function (letters, target) {
let left = 0,
right = letters.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (letters[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// 如果 left 超出范围,则返回第一个字符
return letters[left % letters.length];
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
2148 | 元素计数 | [✓] | 数组 计数 排序 | 🟢 | 🀄️ 🔗 |