【力扣 071】440. 字典序的第K小数字

440. 字典序的第K小数字

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

示例 1:

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/k-th-smallest-in-lexicographical-order
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码实现：

class Solution {
public: 
    int nodeCount(long long cur, int n)  // 统计以cur为根的在合法范围的子树的大小
    {
        long long next = cur + 1;   

        int res = 0;
        while(cur <= n)     // 统计每层的节点
        {
            res += min(next - cur, n - cur + 1);  // 每层节点的右边界为min(n, next)
            cur *= 10;
            next *= 10;
        }
        return res;  // cur为根的子树的节点数目总和 
    }
    int findKthNumber(int n, int k) 
    {
        int cur = 1;
        while(k > 1)
        {
            if(nodeCount(cur, n) >= k)  // cur为根的子树的节点数目总和 >= k
            {
                k --;         // 去掉cur节点         
                cur *= 10;   // 向下搜寻
            }
            else
            {
                k -= nodeCount(cur, n);  // 去掉cur为根的子树的节点数目总和 
                cur ++;                  // 遍历下一种前缀
            }
        }
        return cur;
    }
};

参考资料

1. leetcode 440. 字典序的第K小数字