744.寻找比目标字母大的最小字母

链接：744.寻找比目标字母大的最小字母
难度：Easy
标签：数组、二分查找
简介：给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。

题解 1 - cpp

• 编辑时间：2022-03-18
• 执行用时：20ms
• 内存消耗：15.4MB
• 编程语言：cpp
• 解法介绍：遍历字母表。

class Solution {
   public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        int list[26] = {0};
        for (auto& ch : letters) {
            list[ch - 'a'] = 1;
        }
        target -= 'a';
        for (int i = (target + 1) % 26, cnt = 0; cnt < 26;
             cnt++, i = (i + 1) % 26) {
            if (list[i]) return i + 'a';
        }
        return 'a';
    }
};

题解 2 - cpp

• 编辑时间：2022-04-03
• 执行用时：20ms
• 内存消耗：15.4MB
• 编程语言：cpp
• 解法介绍：二分。

class Solution {
   public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        int l = 0, r = letters.size(), m;
        while (l < r) {
            m = (l + r) >> 1;
            if (letters[m] > target)
                r = m;
            else
                l = m + 1;
        }
        return l == letters.size() ? letters[0] : letters[l];
    }
};