744 Find Smallest Letter Greater Than Target

1. Question

Given a list of sorted charactersletterscontaining only lowercase letters, and given a target lettertarget, find the smallest element in the list that is larger than the given target.
Letters also wrap around. For example, if the target istarget = 'z'andletters = ['a', 'b'], the answer is'a'.
Examples:
1
Input:
2
3
letters = ["c", "f", "j"]
4
target = "a"
5
6
Output: "c"
7
8
9
Input:
10
11
letters = ["c", "f", "j"]
12
target = "c"
13
14
Output: "f"
15
16
17
Input:
18
19
letters = ["c", "f", "j"]
20
target = "d"
21
22
Output: "f"
23
24
25
Input:
26
27
letters = ["c", "f", "j"]
28
target = "g"
29
30
Output: "j"
31
32
33
Input:
34
35
letters = ["c", "f", "j"]
36
target = "j"
37
38
Output: "c"
39
40
41
Input:
42
43
letters = ["c", "f", "j"]
44
target = "k"
45
46
Output: "c"
Copied!
Note:
  1. 1.
    lettershas a length in range[2, 10000].
  2. 2.
    lettersconsists of lowercase letters, and contains at least 2 unique letters.
  3. 3.
    targetis a lowercase letter.

2. Implementation

(1) Binary Search
思路: 非常典型的二分查找 找左边界,思路和search insert position是一样的,其中注意题目要求letters是可以wrap around的 (也就是如果target在数组的插入点是在数组末端的时候,则数组的第一个字母为所求解)
1
class Solution {
2
public char nextGreatestLetter(char[] letters, char target) {
3
int start = 0, end = letters.length - 1, mid = 0;
4
5
while (start + 1 < end) {
6
mid = start + (end - start) / 2;
7
if (letters[mid] <= target) {
8
start = mid + 1;
9
}
10
else {
11
end = mid;
12
}
13
}
14
15
if (letters[start] > target) {
16
return letters[start];
17
}
18
else if (letters[end] > target) {
19
return letters[end];
20
}
21
else {
22
return letters[0];
23
}
24
}
25
}
Copied!

3. Time & Space Complexity

Binary Search: 时间复杂度O(logn), 空间复杂度O(1)