题解 | #字典序#

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        
        while(in.hasNext()){
            solution(in);
        }
    }

    /**
     * 模拟法: 字典树
     * @param in
     */
    private static void solution(Scanner in){
        long n = in.nextLong();
        long k = in.nextLong();
        
        long result = findKthNumber(n, k);
        
        System.out.println(result);
    }

    /**
     * 查找第K个数
     * @param n
     * @param k
     * @return
     */
    private static long findKthNumber(long n, long k){
        // 从根节点下面的第一个结点1开始遍历
        long curr = 1;
        // 从1开始往后按字典序从小到大走k-1步到达的就是 字典序的第K小数字
        k--;

        while(k > 0){
            // 得到以当前结点为根的所有子树节点数目
            long count = countChildNodes(n, curr);
            
            // 如果k大于等于当前根节点下所有子树结点的数目, 就向右侧节点走(->2->3->4->5->6->7->8->9) 字典序上升count位
            if(count <= k){
                // 减去已经遍历的个数
                k -= count;
                // 根节点右移
                curr++;
            }
            // 如果k小于当前根节点下所有子树结点的数目, 说明结果就在当前根节点的子树结点中
            else{
                // 减去根节点的数量1
                k--;
                // 将根结点移动到下一层(每一层10个结点)
                curr *= 10;
            }
        }
        
        // 最终k=0时 得到结果
        return curr;
    }

    /**
     * 计算以curr为根的所有子树节点数目，所有节点的值必须<=n
     * @param n
     * @param curr
     * @return
     */
    private static long countChildNodes(long n, long curr){
        long count = 0;
        long first = curr;
        long last = curr;
        while (first <= n) {
            // 每一层的数目
            count += Math.min(last, n) - first + 1;
            first = first * 10;
            last = last * 10 + 9;
        }
        return count;
    }
}