744. Find Smallest Letter Greater Than Target
Description
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.
Solutions
Solution 1: Binary Search
Since letters
is sorted in non-decreasing order, we can use binary search to find the smallest character that is larger than target
.
We define the left boundary of the binary search as $l = 0$, and the right boundary as $r = n$. For each binary search, we calculate the middle position $mid = (l + r) / 2$. If $letters[mid] > \textit{target}$, it means we need to continue searching in the left half, so we set $r = mid$. Otherwise, we need to continue searching in the right half, so we set $l = mid + 1$.
Finally, we return $letters[l \mod n]$.
The time complexity is $O(\log n)$, where $n$ is the length of letters
. The space complexity is $O(1)$.
1 2 3 4 |
|
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 |
|
1 2 3 4 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|