跳至主要內容

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


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

🟢   🔖  数组 二分查找  🔗 力扣open in new window LeetCodeopen in new window

题目

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,该数组按非递减顺序 排序,以及一个字符 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 <= 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元素计数[✓]数组 计数 排序🟢🀄️open in new window 🔗open in new window