744. Find Smallest Letter Greater Than Target

Leetcode 问题: 744. Find Smallest Letter Greater Than Target
Categories:
Tags:

题目

Given a characters array letters that is sorted in non-decreasing order and a character target, return the smallest character in the array that is larger than target.

Note that the letters wrap around.

For example, if target == 'z' and letters == ['a', 'b'], the answer is 'a'.

给予一个 字母字串阵列 letters，裡面会有数个字母，并按照字母顺序 由小到大（a->z） 排序

传入一个要寻找的字母 target，找寻在字母字串阵列 letters中比这个字母大的 字母

  • 字母一样有出现在字母字串阵列 letters的话，要找比他大的字母，不能同个字母

如果在字母字串阵列 letters中没有找到比字母 target大的字母，则将这个字母字串阵列 letters定为循环字母，回传字母字串阵列 letters中第一个字母

Example

Input: letters = ["c","f","j"], target = "a"
Output: "c"
字母字串阵列 letters c f j
要找寻的字母 target a
比字母 target 大的字母 c 
Input: letters = ["c","f","j"], target = "c"
Output: "f"
字母字串阵列 letters c f j
要找寻的字母 target c
比字母 target 大的字母 f 
Input: letters = ["c","f","j"], target = "d"
Output: "f"
字母字串阵列 letters c f j
要找寻的字母 target d
比字母 target 大的字母 f 
Input: letters = ["c","f","j"], target = "k"
Output: "c"
字母字串阵列 letters c f j
要找寻的字母 target k
比字母 target 大的字母 c

演算法

1. 如果要找寻的字，比字母阵列「最右边」的字母还要大

因为右边已经没有明确比较大的字母了，所以下一个比较大的字母会是「字母阵列」循环的「第一个字母」

字母字串阵列 letters c f j
要找寻的字母 target k
比字母 target 大的字母 c

2. 如果要找寻的字，比字母阵列「最左边」的字母还要小

要找寻的字母，就是「字母阵列」的「第一个字母」

字母字串阵列 letters c f j
要找寻的字母 target a
比字母 target 大的字母 c

3. 二分法切割要检查的字母索引范围

  • 左边字母索引: 0，字母阵列最左方索引
  • 右边字母索引: 字母阵列最右方索引

取左右字母索引，左右逼近到可能出现的最接近的字母，如果「左边字母索引」与「右边字母索引」没有相交，表示还可以再寻找

将字母索引位置切割成一半，拿左右字母索引的平均数当作切割点，可以把数字切割成一半，减少要检查的范围

3. 检查中间切割点

A. 如果 「中间字母」小于或等于「目标字」

「此左边字母索引」可能是要找的字母位置

如果还有更接近「目标字」的索引位置，一定在「中间字母」右方，所以将「左方字母位置」设定为「中间字母 + 1」

B. 如果 「中间字母」大于「目标字」

如果还有更接近「目标字」的索引位置，一定在「中间字母」左方，所以将「右方字母位置」设定为「中间字母 + 1」

答案

JavaScript

使用左边字母索引当作答案

/**
 * @param {character[]} lettersList
 * @param {character} targetLetter
 * @return {character}
 */
var nextGreatestLetter = function(lettersList, targetLetter) {
    // 字母阵列大小
    let letterCount = lettersList.length;
    // 左边字母索引
    let leftLetterIndex = 0;
    // 右边字母索引
    let rightLetterIndex = letterCount - 1;

    if (targetLetter >= lettersList[rightLetterIndex] || targetLetter < lettersList[leftLetterIndex]) {
        // 如果要找寻的字，比字母阵列「最右边」的字母还要大
        // - 因为右边已经没有明确比较大的字母了，所以下一个比较大的字母会是「字母阵列」循环的「第一个字母」
        // 如果要找寻的字，比字母阵列「最左边」的字母还要小
        // - 要找寻的字母，就是「字母阵列」的「第一个字母」
        return lettersList[leftLetterIndex];
    }

    while (leftLetterIndex  <= rightLetterIndex) {
        // 将检查的字母切半，用中间字母索引做检查
        // 中间字母索引
        let middleLetterIndex = leftLetterIndex + Math.floor((rightLetterIndex - leftLetterIndex) / 2);

        if (lettersList[middleLetterIndex] <= targetLetter) {
            // 「中间字母」小于或等于「目标字」，「此左边字母索引」可能是要找的字母位置
            // 如果还有更接近「目标字」的索引位置，一定在「中间字母」右方，所以将「左方字母位置」设定为「中间字母 + 1」
            leftLetterIndex = middleLetterIndex + 1;
        } else {
            // 「中间字母」大于「目标字」
            // 如果还有更接近「目标字」的索引位置，一定在「中间字母」左方，所以将「右方字母位置」设定为「中间字母 + 1」
            rightLetterIndex = middleLetterIndex - 1;
        }
    }

    // 当检查到最后，迴圈中「左方字母位置」会大于「右方字母位置」，表示较大的「左方字母位置」就是要找的字母
    return lettersList[leftLetterIndex];
};

使用右边字母索引当作答案

/**
 * @param {character[]} lettersList
 * @param {character} targetLetter
 * @return {character}
 */
var nextGreatestLetter = function(lettersList, targetLetter) {
    // 字母阵列大小
    let letterCount = lettersList.length;
    // 左边字母索引
    let leftLetterIndex = 0;
    // 右边字母索引
    let rightLetterIndex = letterCount - 1;

    if (targetLetter >= lettersList[rightLetterIndex] || targetLetter < lettersList[leftLetterIndex]) {
        // 如果要找寻的字，比字母阵列「最右边」的字母还要大
        // - 因为右边已经没有明确比较大的字母了，所以下一个比较大的字母会是「字母阵列」循环的「第一个字母」
        // 如果要找寻的字，比字母阵列「最左边」的字母还要小
        // - 要找寻的字母，就是「字母阵列」的「第一个字母」
        return lettersList[leftLetterIndex];
    }

    while ((leftLetterIndex + 1) < rightLetterIndex) {
        // 将检查的字母切半，用中间字母索引做检查
        // 中间字母索引是
        let middleLetterIndex = leftLetterIndex + Math.floor((rightLetterIndex - leftLetterIndex) / 2);

        if (lettersList[middleLetterIndex] <= targetLetter) {
            // 「中间字母」比「目标字」小
            // 如果还有更接近「目标字」的索引位置，一定在「中间字母」右方，所以将「左方字母位置」设定为中间字母
            leftLetterIndex = middleLetterIndex;
        } else {
            // 「中间字母」比「目标字」大，「此右边字母索引」可能是要找的字母位置
            // 如果还有更接近「目标字」的索引位置，一定在「中间字母」左方，所以将「右方字母位置」设定为中间字母
            rightLetterIndex = middleLetterIndex;
        }
    }

    return lettersList[rightLetterIndex];
};

参考资料