给定整数 n 和 k,找到 1 到 n 中字典序第 k 小的数字。
注意:1 ≤ k ≤ n ≤ 1e9。
示例 :
输入:
n: 13 k: 2
输出:
10
解释:
字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9],所以第二小的数字是 10。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/k-th-smallest-in-lexicographical-order
class Solution { public: long get_count( long prefix, long n ){ long count = 0; long cur = prefix; long next = cur + 1; while( cur <= n ){ count += min(n+1, next) - cur; // 以cur为根的子树的总结点数 cur *= 10; next *= 10; // 乘10直接指向相邻子树的最左边儿子 } return count; } int findKthNumber(int n, int k) { long prefix = 1; long next = prefix + 1; int p = 1; // 当前prefix为字典序第p大 while( p < k ){ int count = get_count(prefix, n); // 获取当前prefix为前缀的子树结点总个数 if( p + count > k ){ // 在当前子树内 prefix *= 10; ++ p; }else{ // 不在当前子树内就往下一个前缀找 ++ prefix; p += count; // p + count等于下一个前缀的根结点 } } return prefix; } };