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

🟢   🔖  数组 二分查找  🔗 力扣 LeetCode

题目

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]。

1. 初始化左右指针：
   • 左指针 left = 0，右指针 right = letters.length - 1。
2. 二分查找：
   • 计算中间点 mid = (left + right) / 2 ｜ 0。
   • 如果 letters[mid] > target，更新右边界为 mid - 1。
   • 如果 letters[mid] <= target，更新左边界为 mid + 1。
3. 结束条件：
   • 当 left == right 时，检查对应位置的字符。
   • 如果 left 超过数组范围（即 letters[left] 不存在），返回 letters[0]。
4. 返回结果：
   • 返回大于 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	元素计数	[✓]	数组 计数 排序	🟢	🀄️ 🔗