[LeetCode] 744. Find Smallest Letter Greater Than Target

You are given an array of characters letters that is sorted in non-decreasing order, and a character target. There are at least two different characters in letters.

Return the smallest character in letters that is lexicographically greater than target. If such a character does not exist, return the first character in letters.

Example 1:
Input: letters = [“c”,”f”,”j”], target = “a”
Output: “c”
Explanation: The smallest character that is lexicographically greater than ‘a’ in letters is ‘c’.

Example 2:
Input: letters = [“c”,”f”,”j”], target = “c”
Output: “f”
Explanation: The smallest character that is lexicographically greater than ‘c’ in letters is ‘f’.

Example 3:
Input: letters = [“x”,”x”,”y”,”y”], target = “z”
Output: “x”
Explanation: There are no characters in letters that is lexicographically greater than ‘z’ so we return letters[0].

Constraints:
2 <= letters.length <= 104
letters[i] is a lowercase English letter.
letters is sorted in non-decreasing order.
letters contains at least two different characters.
target is a lowercase English letter.

寻找比目标字母大的最小字母。

给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。

在比较时，字母是依序循环出现的。举个例子：

如果目标字母 target = ‘z’ 并且字符列表为 letters = [‘a’, ‘b’]，则答案返回 ‘a’

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-smallest-letter-greater-than-target
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

最优解是二分法，当然线性的做法也是可以的。

这里有一个 corner case 需要判断，就是如果 target 字母 >= input 数组的最后一个字母，那么我们返回的是 input 数组的首字母。其他环节都是正常的二分法判断。

复杂度

时间O(logn)
空间O(1)

代码

Java实现

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        // corner case
        int n = letters.length;
        if (target >= letters[n - 1]) {
            return letters[0];
        }

        // normal case
        int left = 0;
        int right = n - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (letters[mid] <= target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        if (letters[left] > target) {
            return letters[left];
        }
        return letters[right];
    }
}