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

binary search, 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 <= 10^4
letters[i] 是一个小写字母
letters 按非递减顺序排序
letters 最少包含两个不同的字母
target 是一个小写字母

n小于10^6的情况，线性遍历的实际运行效率更高。

执行用时分布0ms 击败100.00%

python

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        for c in letters:
            if c > target:
                return c
        else:
            return letters[0]

执行用时分布3ms 击败8.94%

python

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        left, right = 0, len(letters)-1
        ans = letters[0]
        while left <= right:
            mid = (left + right) // 2
            if letters[mid] > target:
                ans = letters[mid]
                right = mid -1
            else:
                left = mid + 1
        
        return ans

使用了 C 实现的 bisect 模块，速度会比手写二分快。执行用时分布0ms 击败100.00%

python

import bisect

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        idx = bisect.bisect_right(letters, target)
        return letters[idx % len(letters)]

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

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