核心内容摘要
中文域名转码 在线工具分享
【LetMeFly】
寻找比目标字母大的最小字母遍历或二分力扣题目链接https://leetcode.cn/problems/find-smallest-letter-greater-than-target/给你一个字符数组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 104letters[i]是一个小写字母letters按非递减顺序排序letters最少包含两个不同的字母target是一个小写字母解题方法二分或遍历二分二分查找第一个大于target的元素位置即可upper_bound遍历从头到尾遍历就好。
时间复杂度二分O ( l o g n ) O(log n)O(logn)遍历O ( n ) O(n)O(n)空间复杂度O ( 1 ) O(
O(
AC代码C和Python用的二分因为调库很方便Go、Java和Rust使用的遍历。
C/* * LastEditTime:
13:50:40 */classSolution{public:charnextGreatestLetter(vectorcharletters,chartarget){vectorchar::iterator itupper_bound(letters.begin(),letters.end(),target);returnitletters.end()?letters[0]:*it;}};Python LastEditTime:
13:56:59 fromtypingimportListfrombisectimportbisect_rightclassSolution:defnextGreatestLetter(self,letters:List[str],target:str)-str:idxbisect_right(letters,target)returnletters[0]ifidxlen(letters)elseletters[idx]Java/* * LastEditTime:
14:01:16 */classSolution{publiccharnextGreatestLetter(char[]letters,chartarget){for(inti0;iletters.length;i){if(letters[i]target){returnletters[i];}}returnletters[0];}}Go/* * LastEditTime:
13:59:57 */packagemainfuncnextGreatestLetter(letters[]byte,targetbyte)byte{for_,c:rangeletters{ifctarget{returnc}}returnletters[0]}Rust/* * LastEditTime:
14:03:50 */implSolution{pubfnnext_greatest_letter(letters:Vecchar,target:char)-char{foriin
.letters.len(){ifletters[i]target{returnletters[i];}}letters[0]}}执行用时分布0ms击败
1
00%消耗内存分布
72MB击败
9