leetcode 744. Find Smallest Letter Greater Than Target

￡神魔★判官ぃ 2023-06-21 12:27 68阅读 0赞

[https://leetcode.com/problems/find-smallest-letter-greater-than-target/][https_leetcode.com_problems_find-smallest-letter-greater-than-target]

给定一个元素已经排好序的字符数组以及一个目标字符，找到第一个大于目标字符的元素并返回

## 一、问题分析 ##

测试用例如下：

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"

其中需要注意的是，当target大于字符数组所有元素时，返回字符数组的首元素

## 二、代码实现 ##

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

[https_leetcode.com_problems_find-smallest-letter-greater-than-target]: https://leetcode.com/problems/find-smallest-letter-greater-than-target/