Given a list of sorted characters letterscontaining only lowercase letters, and given a target letter target, find the smallest element in the list that is larger than the given target.
Letters also wrap around. For example, if the target is target = 'z' and letters = ['a', 'b'], the answer is 'a'.
Examples:
Input: letters = ["c", "f", "j"] target = "a" Output: "c" Input: letters = ["c", "f", "j"] target = "c" Output: "f" Input: letters = ["c", "f", "j"] target = "d" Output: "f" Input: letters = ["c", "f", "j"] target = "g" Output: "j" Input: letters = ["c", "f", "j"] target = "j" Output: "c" Input: letters = ["c", "f", "j"] target = "k" Output: "c"
Note:
-
lettershas a length in range[2, 10000]. -
lettersconsists of lowercase letters, and contains at least 2 unique letters. -
targetis a lowercase letter.
给定一个只包含小写字母的有序数组letters 和一个目标字母 target，寻找有序数组里面比目标字母大的最小字母。
数组里字母的顺序是循环的。举个例子，如果目标字母target = 'z' 并且有序数组为 letters = ['a', 'b']，则答案返回 'a'。
示例:
输入: letters = ["c", "f", "j"] target = "a" 输出: "c" 输入: letters = ["c", "f", "j"] target = "c" 输出: "f" 输入: letters = ["c", "f", "j"] target = "d" 输出: "f" 输入: letters = ["c", "f", "j"] target = "g" 输出: "j" 输入: letters = ["c", "f", "j"] target = "j" 输出: "c" 输入: letters = ["c", "f", "j"] target = "k" 输出: "c"
注:
-
letters长度范围在[2, 10000]区间内。 -
letters仅由小写字母组成，最少包含两个不同的字母。 - 目标字母
target是一个小写字母。
Runtime: 220 ms Memory Usage: 19.8 MB
1 class Solution {
2 func nextGreatestLetter(_ letters: [Character], _ target: Character) -> Character {
3 if target >= letters.last!
4 {
5 return letters[0]
6 }
7 var n:Int = letters.count
8 var left:Int = 0
9 var right:Int = n
10 while (left < right)
11 {
12 var mid:Int = left + (right - left) / 2
13 if letters[mid] <= target
14 {
15 left = mid + 1
16 }
17 else
18 {
19 right = mid
20 }
21 }
22 return letters[right]
23 }
24 }
252ms
1 class Solution {
2 func nextGreatestLetter(_ letters: [Character], _ target: Character) -> Character {
3 var left = 0
4 var right = letters.count
5 while left < right {
6 let temp = (left + right) / 2
7 if letters[temp] > target{
8 right = temp
9 }else{
10 left = temp + 1
11 }
12 }
13
14 return letters[left % letters.count]
15 }
16 }
272ms
1 class Solution {
2 func nextGreatestLetter(_ letters: [Character], _ target: Character) -> Character {
3
4 if letters.isEmpty {
5 return target
6 }
7
8 guard let codeTarget = target.unicodeScalars.first?.value else {
9 return target
10 }
11
12 guard let codeLettersLast = letters[letters.count - 1].unicodeScalars.first?.value else {
13 return target
14 }
15
16 if codeLettersLast <= codeTarget {
17
18 return letters[0]
19
20 } else {
21
22 for letter in letters {
23 guard let code = letter.unicodeScalars.first?.value else {
24 continue
25 }
26
27 if code > codeTarget {
28 return letter
29 }
30 }
31
32 }
33
34 return target
35 }
36 }
1 class Solution {
2 func nextGreatestLetter(_ letters: [Character], _ target: Character) -> Character {
3 for letter in letters{
4 if (letter > target){
5 return letter
6 }
7 }
8 return letters[0]
9 }
10
11 }
284ms
1 class Solution {
2 func nextGreatestLetter(_ letters: [Character], _ target: Character) -> Character {
3 let zValue = "z".unicodeScalars.first!.value
4 var targetValue = target.unicodeScalars.first!.value
5 var minV:UInt32 = zValue + 1
6 var minC:Character?
7 for letter in letters{
8 let letterValue = letter.unicodeScalars.first!.value
9 if letterValue > targetValue,
10 letterValue < minV{
11 minV = letterValue
12 minC = letter
13 }
14 }
15 return minC ?? letters[0]
16 }
17 }
288ms
1 class Solution {
2 func nextGreatestLetter(_ letters: [Character], _ target: Character) -> Character {
3 var answer:Character = letters[0]
4
5 for (index,letter) in letters.enumerated(){
6 if letter <= target{
7 if index < letters.count - 1{
8 answer = letters[index + 1]}
9 if index == letters.count - 1{
10 answer = letters[0]
11 }}
12 }
13
14 return answer
15 }
16 }