经典算法实例：寻找比目标字母大的最小字母（一）

我们先来看题目描述给你一个排序后的字符列表 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提示2 letters.length 104letters[i] 是一个小写字母letters 按非递减顺序排序letters 最少包含两个不同的字母target 是一个小写字母解决方案方法一线性查找思路和算法由于给定的列表已经按照递增顺序排序因此可以从左到右遍历列表找到第一个比目标字母大的字母即为比目标字母大的最小字母。如果目标字母小于列表中的最后一个字母则一定可以在列表中找到比目标字母大的最小字母。如果目标字母大于或等于列表中的最后一个字母则列表中不存在比目标字母大的字母根据循环出现的顺序列表的首个字母是比目标字母大的最小字母。代码Python3class Solution: def nextGreatestLetter(self, letters: List[str], target: str) - str: return next((letter for letter in letters if letter target), letters[0])Javaclass Solution { public char nextGreatestLetter(char[] letters, char target) { int length letters.length; char nextGreater letters[0]; for (int i 0; i length; i) { if (letters[i] target) { nextGreater letters[i]; break; } } return nextGreater; } }C#public class Solution { public char NextGreatestLetter(char[] letters, char target) { int length letters.Length; char nextGreater letters[0]; for (int i 0; i length; i) { if (letters[i] target) { nextGreater letters[i]; break; } } return nextGreater; } }复杂度分析时间复杂度O(n) 其中 n 是列表 letters 的长度。需要遍历列表一次寻找比目标字母大的最小字母。空间复杂度O(1) 。