744.Find Smallest Letter Greater Than Target

tags: `Easy`,`Array`,`Binary Search`

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 <= 10⁴
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.

解答

C++







class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        const auto ub = upper_bound(letters.begin(), letters.end(), target);
        return ub == letters.end() ? letters[0] : *ub;
    }
};

Jerry Wu9 June, 2023

Python



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

Yen-Chi ChenFri, Jun 9, 2023



class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        return min([ch for ch in letters if ord(ch) > ord(target)], default=letters[0])

Ron ChenFri, Jun 9, 2023

Java










class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        for(char ch : letters) {
            if(ch - 'a' > target - 'a')
                return ch;
        }

        return letters[0];
    }
}

與 ChatGPT 來來回回改出來的









class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        return new String(letters).chars()
                .filter(ch -> ch > target)
                .mapToObj(ch -> (char) ch)
                .findFirst()
                .orElse(letters[0]);
    }
}