85 lines
2.2 KiB
Markdown
85 lines
2.2 KiB
Markdown
# 毎日一题 - 744. find smallest letter greater than target
|
||
|
||
## 信息卡片
|
||
* 时间：2019-06-17
|
||
* 题目链接：https://leetcode.com/problems/find-smallest-letter-greater-than-target/
|
||
* tag：`Array`
|
||
|
||
## 题目描述
|
||
```
|
||
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.
|
||
```
|
||
|
||
## 思路
|
||
二分查找，提高速度
|
||
要求是查找某一个元素，又是在有序的集合中。
|
||
所以我们可以用二分查找
|
||
1. 排除两种情况；target 小于首元素|| target 大于等于尾元素 => 目标都是首元素
|
||
2. 当target>=letters[mid] 时(我们要的值一定在右边)，调整左区间 min = mid+1;
|
||
3. 当target< letters[mid] 时，调整右区间 max = mid-1;
|
||
4. 循环终止条件是 min > max; 最终返回min位置元素
|
||
|
||
## 建议
|
||
在leetcode上找一个数组稍微长一点的测试用例，在纸上画出整个过程；对理解很有帮助
|
||
|
||
## 参考答案
|
||
```js
|
||
/**
|
||
* @param {character[]} letters
|
||
* @param {character} target
|
||
* @return {character}
|
||
*/
|
||
var nextGreatestLetter = function(letters, target) {
|
||
const length = letters.length
|
||
let min = 0;
|
||
let max = length - 1;
|
||
if(target >= letters[length-1] || target < letters[0]) return letters[0];
|
||
while(min <= max) {
|
||
const mid = (max+min) >> 1
|
||
if(target >= letters[mid]) {
|
||
min = mid + 1;
|
||
} else {
|
||
max = mid - 1;
|
||
}
|
||
}
|
||
return letters[min]
|
||
};
|
||
```
|