440. 字典序的第K小数字

leetcode刷题

给定整数 n 和 k，找到 1 到 n 中字典序第 k 小的数字。
注意：1 ≤ k ≤ n ≤ 109。
示例 :
输入:
n: 13 k: 2
输出:
10
解释:
字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。

这是一道字节常考的算法题
**解题思路：10叉树
记录当前结点的个数，如果当前结点的个数num>k的话，则在子节点中去找，子节点就是x10，然后k要减去当前节点的个数num；如果当前结点数num<k的话，说明还太小呢，所以就向右走，cur++，k–；

**

class Solution {
    public int findKthNumber(int n, int k) {
        //字典序列   10叉树

        //思路：前序遍历；每次记录子节点的数量num，如果num>k了，说明在子节点中；否则的话就在右边找

        int cur = 1;
        //1 ≤ k ≤ n ≤ 109
        while(k>1){
            int num = getCount(n,cur,cur+1);
            if(num<k){//如果小于了，则前序遍历-往右走
                cur++;
                k-=num;
            }else{//如果大于了，则在子节点中-往下走，，下的话就是10叉树
                cur*=10;
                k-=1;
            }
        }
        return cur;
    }
    private int getCount(int n,long first,long last){//设置为num，是因为*10之后怕溢出
        int count = 0;
        while(first <=n){
            count+=Math.min(last,n+1)-first;
            first*=10;
            last*=10;
        }
        return count;
    }
}