C#LeetCode刷题之#744-寻找比目标字母大的最小字母（Find Smallest Letter Greater Than Target）

问题

给定一个只包含小写字母的有序数组letters 和一个目标字母 target，寻找有序数组里面比目标字母大的最小字母。

数组里字母的顺序是循环的。举个例子，如果目标字母target = ‘z’ 并且有序数组为 letters = [‘a’, ‘b’]，则答案返回 ‘a’。

输入:
letters = [“c”, “f”, “j”]
target = “a”

输出: “c”

输入:
letters = [“c”, “f”, “j”]
target = “c”

输出: “f”

输入:
letters = [“c”, “f”, “j”]
target = “d”

输出: “f”

输入:
letters = [“c”, “f”, “j”]
target = “g”

输出: “j”

输入:
letters = [“c”, “f”, “j”]
target = “j”

输出: “c”

输入:
letters = [“c”, “f”, “j”]
target = “k”

输出: “c”

注:

• letters长度范围在[2, 10000]区间内。
• letters 仅由小写字母组成，最少包含两个不同的字母。
• 目标字母target 是一个小写字母。

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’.

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.

示例

public class Program {

    public static void Main(string[] args) {
        var letters = new char[] { 'c', 'f', 'j' };
        var target = 'd';

        var res = NextGreatestLetter(letters, target);
        Console.WriteLine(res);

        letters = new char[] { 'a', 'c', 'f', 'j' };
        target = 'b';

        res = NextGreatestLetter2(letters, target);
        Console.WriteLine(res);

        Console.ReadKey();
    }

    private static char NextGreatestLetter(char[] letters, char target) {
        //暴力法
        foreach(var c in letters) {
            if(c > target) return c;
        }
        return letters[0];
    }

    private static char NextGreatestLetter2(char[] letters, char target) {
        //二分法
        var low = 0;
        var high = letters.Length - 1;
        var mid = 0;
        while(low <= high) {
            mid = low + (high - low) / 2;
            if(letters[mid] > target) {
                high = mid - 1;
            } else if(letters[mid] <= target) {
                low = mid + 1;
            }
        }
        if(low >= letters.Length) low = 0;
        return letters[low];
    }

}

以上给出2种算法实现，以下是这个案例的输出结果：

f
c

分析：

显而易见，NextGreatestLetter 的时间复杂度为： ​ ，NextGreatestLetter2 的时间复杂度为：  。