[leetcode/lintcode 题解] 算法面试真题详解：字典序的第K小数字

描述
给定整数n和k，找到按字典序排序的第k个最小整数，范围从1到n。
1 ≤ k ≤ n ≤ 1e9.

在线评测地址：领扣题库官网

样例1
输入：200,18
输出：114
解释：1,10,100,101,102,103,104,105,106,107,108,109,11,110,111,112,113,114，第十八个是114。

样例2
输入：13，2
输出：10
解释：按字典序排列顺序为 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], 所以第二小的数字为10。

考点：

• 字符串
• 枚举

题解：
字符串的构造类似于十叉树，用k减去子节点的个数，step表示以curr开头至curr+1开头间的字符串数量，step是否小于等于k，如果是，我们cur自增1，k减去step；如果不是，说明要求的数字在子节点中，我们此时cur乘以10，k自减1，以此类推，直到k为0推出循环，此时cur即为所求。
代码

public class Solution {
    /**
     * @param n: a integer
     * @param k: a integer
     * @return: return a integer
     */
    public int findKthNumber(int n, int k) {
        int curr = 1;
        k = k - 1;
        while (k > 0) {
            int steps = calSteps(n, curr, curr + 1);
            if (steps <= k) {   //如果不在当前层，减去steps
                curr += 1;      
                k -= steps;  
            } 
            else {              //说明在当前层,curr*10缩小搜索范围继续查找
                curr *= 10;
                k -= 1;
            }
        }
        return curr;
    }
    //use long in case of overflow
    public int calSteps(int n, long n1, long n2) { //计算curr开头和curr+1开头之间的字符串数量
        int steps = 0;
        while (n1 <= n) {
            steps += Math.min(n + 1, n2) - n1;  //每次加上当前的字符串数量
            n1 *= 10;       //每次均扩大10倍
            n2 *= 10;
        }
        return steps;
    }
}

更多题解参考：九章官网solution