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

參考資料