### 题目描述 给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。 在比较时，字母是依序循环出现的。举个例子： - 如果目标字母 target = 'z' 并且字符列表为 letters = ['a', 'b']，则答案返回 'a' ### 输入输出 #### 示例1 ``` 输入: letters = ["c", "f", "j"]，target = "a" 输出: "c" ``` #### 示例2 ``` 输入: letters = ["c","f","j"], target = "c" 输出: "f" ``` #### 示例3 ``` 输入: letters = ["c","f","j"], target = "d" 输出: "f" ``` ### 题目解答 #### 思路 对于该问题，可以将字母看成数字。那么问题就转变成，在一个非降序排列的数组中，给定一个数字，找到比该数字大的一个数字。 如果在该数组中没有比它大的数字，那么返回该数组的第一个数字。 因此对于该查找问题，可以选择顺序查找或者二分查找的方式。 **顺序查找复杂度：** 时间复杂度：$$O(n)$$ **二分查找复杂度：** 时间复杂度：$$O(logn)$$ #### 代码实现 ```python def nextGreatestLetter(self, letters: List[str], target: str) -> str: left = 0 right = len(letters) - 1 while left < right: mid = left + (right - left) // 2 if letters[mid] <= target: left = mid + 1 else: right = mid if left == len(letters) - 1 and letters[left] <= target: return letters[0] else: return letters[left] ``` 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复