FindSmallestLetterGreaterThanTarget [source code]

public class FindSmallestLetterGreaterThanTarget {
static
/******************************************************************************/
class Solution {
    public char nextGreatestLetter(char[] letters_, char target) {
        assert letters_.length >= 2;
        char[] letters = new char[2 * letters_.length];
        for (int i = 0; i < letters.length; i++) 
            letters[i] = letters_[i % letters_.length];
        int lo = 0, hi = letters.length - 1, res = -1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (target < letters[mid])
                hi = mid - 1;
            else if (target > letters[mid])
                lo = mid + 1;
            else {
                while (mid < letters.length && letters[mid] == target)
                    mid++;
                return letters[mid];
            }
        }
        // Terminating condition on LO is key to binary search
        return letters[lo % letters.length];
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        FindSmallestLetterGreaterThanTarget.Solution tester = new FindSmallestLetterGreaterThanTarget.Solution();
        char[][] inputs = {
            {'c','f','j'}, {'a','c'},
            {'c','f','j'}, {'c','f'},
            {'c','f','j'}, {'d','f'},
            {'c','f','j'}, {'g','j'},
            {'c','f','j'}, {'j','c'},
            {'c','f','j'}, {'k','c'},
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            char[] letters = inputs[2 * i];
            char target = inputs[2 * i + 1][0], ans = inputs[2 * i + 1][1];
            System.out.println (Printer.separator ());
            char output = tester.nextGreatestLetter (letters, target);
            System.out.printf ("%s and %c -> %s, expected: %c\n",
                Printer.array (letters), target, Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
            );
        }
    }
}

看起来是一个很简单的题目, 但是这个wrap好像让问题变得复杂了一些;

当然你也可以直接一个linear来做, 不过这种做法实际面试的时候肯定会被喷;

以前解决wrap/cyclic的常见方法, 就是直接double; 这个方法在这一题适用吗?

首先, 重温一下binary search的经典写法:

    public static int indexOf(int[] a, int key) {  
        int lo = 0;  
        int hi = a.length - 1;  
        while (lo <= hi) {  
            // Key is in a[lo..hi] or not present.  
            int mid = lo + (hi - lo) / 2;  
            if      (key < a[mid]) hi = mid - 1;  
            else if (key > a[mid]) lo = mid + 1;  
            else return mid;  
        }  
        return -1;  
    }

脑子空想完全是浪费时间, 直接按照下面给出来的例子, 动笔画了一下, 感觉好像double可以搞定; 我认为double搞不定的原因是因为double了之后可能会破坏掉sorted的性质; 但是仔细想想(结合笔算), 好像并不存在这个问题, 因为对于binary search来说, double了一下之后, 其实就是多了第一个iteration而已; 往后的iteration, 还是在sorted的前提下进行的;

最后超时了一点还是AC了, 速度是14ms (NA). 这个题目总体来说确实不难, 不过我对binary search还是忘记太多了, 这个题目帮忙回忆了一些; 注意这题细节上稍微要注意一点的地方就是一个是hit怎么处理: 因为我们要找的是greater, 所以要有一个向后移动的过程; 这里注意两个问题, 首先, 如果是一个hit的target, 那么在double之后的两段, hit的位置肯定是在第一段里面; 所以当你hit之后, 向右移动的时候, 记得要判断的是相等而不是大于小于; 因为:

• 第一个iteration肯定进入第一段
• 向右平移的时候判断的是相等
  所以最后这里是不需要额外wrap一下的;

另外一个问题是, 最后不能直接返回lo, 因为如果是一个右边超界的(过大)的target, 那么第一个iteration肯定会进入第二段, 然后最后的lo表示的是insertion position, 这个position这个时候是超界的, 所以要继续多wrap一下;

editorial3给出了一个binary search的解法:

Like in Approach #2, we want to find something larger than target in a sorted array. This is ideal for a binary search: Let's find the rightmost position to insert target into letters so that it remains sorted.
Our binary search (a typical one) proceeds in a number of rounds. At each round, let's maintain the loop invariant that the answer must be in the interval [lo, hi]. Let mi = (lo + hi) / 2. If letters[mi] <= target, then we must insert it in the interval [mi + 1, hi]. Otherwise, we must insert it in the interval [lo, mi].
At the end, if our insertion position says to insert target into the last position letters.length, we return letters[0] instead. This is what the modulo operation does.

class Solution {  
    public char nextGreatestLetter(char[] letters, char target) {  
        int lo = 0, hi = letters.length;  
        while (lo < hi) {  
            int mi = lo + (hi - lo) / 2;  
            if (letters[mi] <= target) lo = mi + 1;  
            else hi = mi;  
        }  
        return letters[lo % letters.length];  
    }  
}

这里他的写法跟我的有一些区别:

• 他使用的是开区间写法, 所以header里面判断的条件不包含lo == hi;
• 他没有使用double做法来解决cyclic问题;
• 他使用的是二叉写法, 而不是三叉写法; 这样就避免了对于hit情况要特殊处理的问题; 但是二叉写法的一个问题是往往对于invariant的设计要格外小心一些;

首先, 大部分的二叉写法都是判断leq and >, 这里也是一样; 核心逻辑是if (letters[mi] <= target) lo = mi + 1;, 满足ans (smallest greater letter) in [lo, hi]的invariant (严格来说应该是[lo, hi)). 因为我们要求的是>的letter, 所以如果[mid]是leq, 那么直接让下一个区间的[lo, hi)就不包含mid就行了; 这个逻辑本身不难理解; 反正binary search问题很多时候就是要在invariant上面纠结, 慢慢就适应了;

另外一个遗留问题就是, 开区间写法下的mid的计算跟闭区间写法下的mid的计算区别到底有多大? 其实你自己动手笔算一下: 比如长度为3的array, 和长度为2的array, 你分别计算一下就知道, 开区间下的mid的计算, 差别最多也就是比闭区间写法多计算一个iteration而已; 因为/2的truncate性质, 最后其实收敛的地方都是一样的;

这个是discussion里面一个类似的写法:

@xpfxzxc said in Easy Binary Search in Java - O(log(n)) time:

I can do better.

class Solution {  
public:  
    char nextGreatestLetter(vector<char>& letters, char target) {  
        int n = letters.size(), lo = 0, hi = n;  
        while (lo < hi) {  
            int mid = lo + (hi - lo) / 2;  
            if (letters[mid] > target) hi = mid;  
            else                       lo = mid + 1;  
        }  
        return letters[lo % n];  
    }  
};

不过他这个感觉比如editorial写法更加易懂: 对invariant的强调不如editorial的明显;

不过看到这里正好想一下, 好像对于上面的invariant的区间的写法, 我自己的理解是错误的, 因为[lo, hi)的看法其实不好解释hi = mid这一个branch; 反而, [lo, hi]更容易解释: 如果[mid]满足>target, 那么我们最后要找的结果不可能比[mid]大, 所以让mid成为新的hi就行了;

事实上, 当你看到这题要求你用binary search的时候, 有没有想过直接用library里面的? 事实上这题还真的可以这么做:

@ManuelP said in Java 2 lines O(log n):

public char nextGreatestLetter(char[] letters, char target) {  
    int i = Arrays.binarySearch(letters, (char) (target + 1));  
    return letters[i >= 0 ? i : ~i % letters.length];  
}

Sadly if an element appears several times, Java's Arrays.binarySearch might find any of them. There's no way to ask for the first or last occurrence like you can in some other languages. So I can't ask "Where's the last occurrence of the target?" and then just look at the letter after it.

But if I don't ask for the target letter but instead for the next larger letter, that doesn't matter. If it exists in the array, I don't care which one I'm shown. I just return the one I'm shown. And if it doesn't exist, then I'm shown the location where it would be inserted, which is where the next even larger letter is or where the string ends.

For example when the target is e, I ask "Where is an f?". If there is one, then I get an index i >= 0 where I can simply grab it. And if there isn't one, then ~i gives me the index where it would be inserted, i.e., where the next even larger letter (in my example that's g, h, i, or whatever the next existing letter is) is or where the string ends. For the latter case I wrap around by using % letters.length.

学习他的技巧除外, 还要看看他对于java本身的这个实现的细节的描述, 就是在多个hit的情况下, 最后返回的这个结果的位置是没有办法保证的;

好像闭区间的写法也是可以的:

    public char nextGreatestLetter(char[] letters, char target) {  
        // Arrays.sort(letters); // sorted  
        int n = letters.length;  
        int l = 0, r = n - 1;  
        while (l <= r) {  
            int m = l + (r - l) / 2;  
            if (letters[m] > target) r = m - 1;  
            else l = m + 1;  
        }  
        return l == n ? letters[0] : letters[l];  
    }

同样, 这个写法还是二叉, 依赖的invariant也是类似editorial里面的那个invariant, 所以最后看起来代码好像有点区别(比如l和r的更新方式), 但是实际上本质是一样的;

submission暂时还看不到;

Problem Description

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

Examples:

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.

Difficulty:Easy
Total Accepted:6.7K
Total Submissions:14K
Contributor:imsure
Companies
linkedin
Related Topics
binary search

Hide Hint 1

Try to find whether each of 26 next letters are in the given string array.