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

问题

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

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

注:

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

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 的时间复杂度为： C#LeetCode刷题之#744-寻找比目标字母大的最小字母（Find Smallest Letter Greater Than Target）-LMLPHP ，NextGreatestLetter2 的时间复杂度为：。