JAVA练习226-字典序的第K小数字

给定整数 n 和 k，返回 [1, n] 中字典序第 k 小的数字。

输入: n = 13, k = 2
输出: 10
解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。

输入: n = 1, k = 1
输出: 1

1 <= k <= n <= 10^9

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/k-th-smallest-in-lexicographical-order

根据字典树定义可以知道，我们按照数字的位数进行构造，先序遍历的结果一定是字典序的排列。而这里其实不用构造真的字典树，可以直接用数字进行模拟，令第 m 小的的数字为 node(m)，那么大于该数字的数量为 n - node(m)，我们令 node(m)的子树个数为 cnt，那么该子树满足：

当 cnt <= n - node(m) 时，那么目标节点一定不在该子树中，继续从 node(m) 后遍历 k - m 个节点遍历即可当 cnt > n - node(m) 时，目标节点一定在该子树中，继续遍历该子树

关于 cnt，我们令层数为 i，每层第一个孩子节点为 first(i)，最后一个孩子节点为 last(i)，由树的定义的可以知道，first(i) = first(i-1) * 10，last(i) = last(i-1) * 10 + 9，第 i 层的节点数就为 last(i) - first(i) + 1 个，因为所有节点都要满足小于等于 n，所以最后一个节点就为 last(i) 和 n 的最小值，根据以上公式进行遍历就可以得到 cnt。

时间复杂度：O(log² n)
空间复杂度：O(1)

class Solution {
    public int findKthNumber(int n, int k) {
        //初始值
        int origin = 1;
        --k;
        //遍历
        while(k > 0){
            //获取子树个数
            int cnt = getCnt(origin, n);
            //不在子树中
            if(cnt <= k){
                k -= cnt;
                origin++;
            }
            //在子树中
            else{
                origin *= 10;
                --k;
            }
        }
        return origin;
    }

    //获取子树节点数
    public int getCnt(int i, long n) {
        //定义节点数，第一个孩子节点，最后一个孩子节点
        long cnt = 0, first = i, last = i;
        //遍历，计算
        while (first <= n) {
            cnt += Math.min(last, n) - first + 1;
            first *= 10;
            last = last * 10 + 9;
        }
        return (int)cnt;
    }
}