LeetCode 744. Find Smallest Letter Greater Than Target (寻找比目标字母大的最小字母)

客官°小女子只卖身不卖艺 2023-08-17 16:45 69阅读 0赞

题目标签：Binary Search

题目给了我们一组字母，让我们找出比 target 大的最小的那个字母。

利用 binary search，如果mid 比 target 小，或者等于，那么移到右半边；

如果 mid 比target 大，那么移到左半边，这里要包括mid，因为mid 可能是那个要找的字母。

这里还要检查一个可能，如果 target 是 z， 那么 最小的那个字母，就是 比z 大的字母。

来覆盖这个可能性，可以用 target 比 array 里最后那个字母， 如果target大的话， 那么返回 第一个字母。

Java Solution:

Runtime:  0 ms, faster than 100 %

Memory Usage: 39 MB, less than 85 %

完成日期：08/01/2019

关键点：用 target 比 letters\[n-1\] 来包括 “letters also wrap around”

class Solution {
        public char nextGreatestLetter(char[] letters, char target) {
            
            int n = letters.length;
            
            if(target >= letters[n - 1])
                return letters[0];
            
            int left = 0;
            int right = n - 1;
            
            while(left < right) {
                int mid = left + (right - left) / 2;
                
                if(letters[mid] <= target)
                    left = mid + 1;
                else if(letters[mid] > target)
                    right = mid;
            }
            
            return letters[right];
        }
    }

参考资料：LeetCode Discuss[  
][Link 1]

LeetCode 题目列表 - [LeetCode Questions List][]

题目来源：https://leetcode.com/

转载于:https://www.cnblogs.com/jimmycheng/p/11297082.html

[Link 1]: https://leetcode.com/problems/daily-temperatures/discuss/?currentPage=1&orderBy=recent_activity&query=
[LeetCode Questions List]: http://www.cnblogs.com/jimmycheng/p/7119334.html