九章算法 | Hulu面经：字典序的第K小数字

描述

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

1 ≤ k ≤ n ≤ 1e9.

在线评测地址

LintCode 领扣

样例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; 
    } 
} 

更多题解参考：九章算法