- 题目描述
- 解题思路
- 执行结果
题目描述
-
寻找比目标字母大的最小字母
给你一个字符数组 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 <= 104 letters[i] 是一个小写字母 letters 按非递减顺序排序 letters 最少包含两个不同的字母 target 是一个小写字母
解题思路
法1
方法1:二分法
根据题目描述,数组是一个有序数组,对于有序数组的查找,我们通常使用的是二分法进行查找,可以极大的优化性能
-
查找目标:nums[n-1]<=x&&num[n]>x -
定义二分法,如果再目标的左边,那么将左边的范围分成两份,对比中间的数值,如果小于于,就对右边的数组进行二分,持续循环直到找到目标值为止
-
时间复杂度(O(logn)) -
空间复杂度(O(1))
执行结果
法1
二分查找的思想。由于数组letters是按非递减顺序排序的，我们可以使用二分查找来找到大于target的最小字符。
我们初始化左指针left为0，右指针right为len(letters)-1。如果target大于或等于letters的最后一个字符，那么返回letters的第一个字符。
然后我们开始二分查找，每次取中间的字符mid。如果letters[mid]小于等于target，则说明目标字符在mid的右边，将左指针left更新为mid+1。否则，说明目标字符在mid的左边或就是mid本身，将右指针right更新为mid-1。
最终，当二分查找结束时，左指针left指向的位置就是大于target的最小字符的位置，我们将其返回作为结果。
func nextGreatestLetter(letters []byte, target byte) byte {
n := len(letters)
left := 0
right := n - 1
// 如果 target 大于或等于 letters 的最后一个字符，
// 则返回 letters 的第一个字符
if target >= letters[right] {
return letters[0]
}
// 使用二分查找找到大于 target 的最小字符
for left <= right {
mid := left + (right-left)/2
if letters[mid] <= target {
left = mid + 1
} else {
right = mid - 1
}
}
return letters[left]
}
执行结果： 通过 显示详情 查看示例代码 添加备注
执行用时： 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗： 2.5 MB , 在所有 Go 提交中击败了 71.15% 的用户 通过测试用例： 167 / 167 炫耀一下:
本文由 mdnice 多平台发布
