LWC 62：744. Find Smallest Letter Greater Than Target
LWC 62：744. Find Smallest Letter Greater Than Target
LWC 62：744. Find Smallest Letter Greater Than Target
传送门：744. Find Smallest Letter Greater Than Target
Problem:
Given a list of sorted characters letters containing 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:
letters has a length in range [2, 10000].
letters consists of lowercase letters, and contains at least 2 unique letters.
target is a lowercase letter.
思路： 因为wrap around，所以当给的target大于最大元素，就取集合中最小字符。否则，取大于target的第一个元素。（集合需要排序）
Java版：
public char nextGreatestLetter(char[] letters, char target) {
Set<Character> set = new HashSet<>();
for (char c : letters) set.add(c);
char[] let = new char[set.size()];
int i = 0;
for (char c : set) {
let[i++] = c;
}
Arrays.sort(let);
for (int j = 0; j < let.length; ++j) {
if (let[j] > target) return let[j];
}
return let[0];
}实际上是不需要去重的，代码如下：
public char nextGreatestLetter(char[] letters, char target) {
Arrays.sort(letters);
for (int j = 0; j < letters.length; ++j) {
if (letters[j] > target) return letters[j];
}
return letters[0];
}因为集合有序，所以可以使用upper_bound的二分查找，代码如下：
public char nextGreatestLetter(char[] letters, char target) {
Arrays.sort(letters);
return letters[upperBound(letters, target)];
}
public int upperBound(char[] letters, char target) {
int l = 0;
int r = letters.length - 1;
while (l < r) {
int m = l + (r - l) / 2;
if (letters[m] <= target) {
l = m + 1;
}
else{
r = m;
}
}
if (letters[r] > target) return r;
else return 0;
}当然你也可以使用Java自家的二分查找接口，但可惜的是，官方接口不支持重复元素集合的准确查找（会出错），所以在使用之前需要对元素去重。
代码如下：
public char nextGreatestLetter(char[] letters, char target) {
Set<Character> set = new HashSet<>();
for (char c : letters) set.add(c);
char[] let = new char[set.size()];
int i = 0;
for (char c : set) {
let[i++] = c;
}
Arrays.sort(let);
int idx = Arrays.binarySearch(let, target);
if (idx >= 0){
if (idx + 1 >= let.length) return let[0];
else return let[idx + 1];
}
else {
idx = -idx - 1;
if (idx == let.length) return let[0];
else return let[idx];
}
}Python版本：
def nextGreatestLetter(self, letters, target):
"""
:type letters: List[str]
:type target: str
:rtype: str
"""
sorted(letters)
for l in letters:
if (target < l): return l
return letters[0]自带的库也是非常方便：
def nextGreatestLetter(self, letters, target):
"""
:type letters: List[str]
:type target: str
:rtype: str
"""
pos = bisect.bisect_right(letters, target)
return letters[0] if pos == len(letters) else letters[pos] 腾讯云开发者
