2019-06-17.md

毎日一题 - 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上找一个数组稍微长一点的测试用例，在纸上画出整个过程；对理解很有帮助

参考答案

/**
 * @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]
};