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 <= 104letters[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#
1
2
3
4
5
6
7
8
9
10
| class Solution:
def nextGreatestLetter(self, letters: List[str], target: str) -> str:
left, right = 0, len(letters)
while left < right:
mid = (left + right) >> 1
if ord(letters[mid]) > ord(target):
right = mid
else:
left = mid + 1
return letters[left % len(letters)]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public char nextGreatestLetter(char[] letters, char target) {
int left = 0, right = letters.length;
while (left < right) {
int mid = (left + right) >> 1;
if (letters[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
return letters[left % letters.length];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
int left = 0, right = letters.size();
while (left < right) {
int mid = left + right >> 1;
if (letters[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
return letters[left % letters.size()];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
| func nextGreatestLetter(letters []byte, target byte) byte {
left, right := 0, len(letters)
for left < right {
mid := (left + right) >> 1
if letters[mid] > target {
right = mid
} else {
left = mid + 1
}
}
return letters[left%len(letters)]
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| function nextGreatestLetter(letters: string[], target: string): string {
const n = letters.length;
let left = 0;
let right = letters.length;
while (left < right) {
let mid = (left + right) >>> 1;
if (letters[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
return letters[left % n];
}
|
1
2
3
4
5
6
7
8
| impl Solution {
pub fn next_greatest_letter(letters: Vec<char>, target: char) -> char {
*letters
.iter()
.find(|&&c| c > target)
.unwrap_or(&letters[0])
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
/**
* @param String[] $letters
* @param String $target
* @return String
*/
function nextGreatestLetter($letters, $target) {
$left = 0;
$right = count($letters);
while ($left <= $right) {
$mid = floor($left + ($right - $left) / 2);
if ($letters[$mid] > $target) {
$right = $mid - 1;
} else {
$left = $mid + 1;
}
}
if ($left >= count($letters)) {
return $letters[0];
} else {
return $letters[$left];
}
}
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| impl Solution {
pub fn next_greatest_letter(letters: Vec<char>, target: char) -> char {
let n = letters.len();
let mut left = 0;
let mut right = n;
while left < right {
let mid = left + (right - left) / 2;
if letters[mid] > target {
right = mid;
} else {
left = mid + 1;
}
}
letters[left % n]
}
}
|
