# LWC 62：744. Find Smallest Letter Greater Than Target

## LWC 62：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.

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];
}```

```    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;
}```

```    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] ```

0 条评论

## 相关文章

15150

10120

468110

29860

### 第十九天 集合-Map接口容器工具类集合框架总结【悟空教程】

Map集合的特点，如是否可重复，是否有序仅作用在键上，如HashMap集合的键不得重复，值可以重复。

24630

34340

46610

### 读 Java Arrays 源码 笔记

Arrays.java是Java中用来操作数组的类。使用这个工具类可以减少平常很多的工作量。了解其实现，可以避免一些错误的用法。 它提供的操作包括： 排序 so...

385120

### 读 Java Arrays 源码 笔记

Arrays.java是Java中用来操作数组的类。使用这个工具类可以减少平常很多的工作量。了解其实现，可以避免一些错误的用法。

11120

6920