给定整数 n 和 k，找到 1 到 n 中字典序第 k 小的数字。
注意：1 ≤ k ≤ n ≤ 109。

这个题目真的好难，看了题解都看了一个多小时，其实很费力的理解了。但是为什么一模一样的代码，别人的全部通过了，我只能通过部分？很费解啊。
图片说明

问题的关键是要看懂这个图，并且要知道比如以1为根的节点的数量等于第二层+第三层+第四层的数量，
而第二层的数量=20-10（在满层的情况的下）
第三层的数量=200-100（在满层的情况的下）
所以这也是为什么代码中一直要*10进行循环往复的原因。也是因为当时我没有仔细分析不理解的原因。
三个注意点：

  • 十叉完全树
  • 孩子节点为x*10， 兄弟节点为x+1
  • 孩子的数量为（x+1）10 - x10
  • 孙子的数量继续求解 
class Solution {

    //这道题目是10叉前缀数目，并且是一个完全的十叉树，因此在求解一数x为前缀的数的时候可以用兄弟节点来进行求解。
    //先找到该树中包含的个数，如果大于K，那么结果在其字数中，使用前缀遍历的方法进行遍历去找到我们想要的值。

    public int getCount(int prefix, int n){
        //我们需要知道在prefix这棵前缀完全十叉数上的个数，方便统计是否满足k。同时需要用n来进行限制，因为有n的存在，这棵树不一定是满的。同时这棵树的节点个数等于孩子节点的数量+孙子节点的数量，我们画个图可以看到这些数量都是满足规律的。
        int cur = prefix;
        int next = prefix +1;
        int count = 0;
        while(cur <= n){
            count += (Math.min(n+1, next) -cur);//孩子节点的数量，其中也包含了prefix本身这个节点，同时因为不一定是满二叉树，需要上限制n做一个限制，至于为什么是n+1，是因为n-cur+1才是数量
            cur = cur*10; //为了求孙子节点的数量
            next = next*10;//为了求孙子节点的数量
        }
        return count;
    }

    public int findKthNumber(int n, int k) {
        //这里是真正的求解

        int p=1;//指明待访问的第p排序数
        int prefix = 1;//指明待访问的前缀树