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 的时间复杂度为:
。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/4001。