Awesome java solution


  • 0
    F

    First, we need a help function to do something:

        private int findKthNumber(long p, long q, long n) {
            int result = 0;
            while (p <= n) {
                result += Math.min(q, n + 1) - p;
                p *= 10;
                q *= 10;
            }
            return result;
        }
    

    The use of the upper function is to get the number of numbers in range [p,min(q,n+1)) in lexicographical order. Because the number must be <=n, so it must <n+1.
    Now, given a lower bound p(inclusive), a upper bound q(exclusive), and with a constraint n(inclusive), we can easily find the number of numbers which are in range [p,min(q,n+1)) in lexicographical order by using the upper function.
    Moreover, we use long to avoid overflow, as 10*q, 10*q, n+1 may be greater than Integer.MAX_VALUE, of course, n is not necessary, but if n is Integer.MAX_VALUE(not in this problem), may cause overflow.
    Next, comes the main function:

        public int findKthNumber(int n, int k) {
            int result = 1;
            while (k > 1) {
                int count = findKthNumber(result, result + 1, n);
                if (count < k) {
                    result++;
                    k -= count;
                } else {
                    result *= 10;
                    k--;
                }
            }
            return result;
        }
    

    if k>count, we scan from left to right by increase result
    if k<=count, we scan from up to bottom by multiply result by 10
    very easy to understand, hope helps


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.