首页 > itarticle > 744. find smallest letter greater than target

744. find smallest letter greater than target

admin 11月 13, 2020 0

explanation

find smallest elements that is larger than target
Letters also wrap around. For example, if the target is target = ‘z’ and letters = [‘a’, ‘b’], the answer is ‘a’.

如果没有提warp around，{a, b , c} target c，需要问面试官这种情况下，返回什么

code

class  {
    public char nextGreatestLetter(char[] letters, char target){
        
        // if (letters == null || letters.length == 0) {
        //     throw new Exception("letters is empty.");
        // }
        int start = 0, end = letters.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (letters[mid] <= target) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }

        if (letters[start] > target) {
            return letters[start];
        } else if (letters[end] > target) {
            return letters[end];
        } else { // start 和 end 都 <= target， end 不可能在中间， 只可能在最后一位
            return letters[0];
        }


    }
}