hard题 给定1个n和一个k 求从1到n中字典序第k小的数字是哪个
借助于树的思想
则该树的前序遍历所得到的答案即为字典序从小到大的排序
这里需要明确一个操作 即以prefix为开头的数字在前limt个数中有多少个
比如给定prefix=14 limit=2000
* 2位数：14为1个
* 3位数：140-149这10个
* 4位数：1400-1499 这100个
记prefix长度为n limit长度为m
不失一般性的考虑
* 位数为n的数：仅有x本身，共1个;
* 位数为n+1<m的数：有x0到x9，共10个;
* 位数为n+2<m的数字：有x00到x99，共100个;
* ...
* 位数为m的数字，此时根据limit长度与prefix等同的前缀u和prefix的大小关系，进一步分情况讨论(举个?，当limit=12456，prefix=123时，u=124，两者位数相差k=2):
* u<prefix:此时所有位数为m的数均大于limit，合法个数为0
* u=prefix:此时所有位数为m的数部分符合要求 合法个数为limit-prefix*10的k次方+1 ?:limit=12345 prefix=123 合法的有12300 12301 ... 12345
* u>x:此时全合法 合法个数为10的k次方 ?:limit=34567 prefix=12345 合法的有12300 - 12399
此时根据该函数 可以从最小的前缀1开始枚举，假设当前枚举到前缀x，根据cnt=getCnt(prefix,n)与k的大小关系进行分情况讨论
* cnt<k:说明所有以x为前缀的数组均可以跳过，prefix自增，k减去cnt。含义为从下一个数值比prefix大的前缀中找目标值。
* cnt>=k:说明目标值的前缀必然为prefix，此时我们需要在以prefix为前缀的前提下寻找目标值。此时让prefix乘10，k--（代表跳过了prefix本身）。含义为从下一个字典序比prefix大的前缀中寻找目标值，即往?的下一层找
class Solution
{
public:
ll getCnt(ll prefix, ll n)
{
//前n个数中 以prefix为前缀的数字有多少个
ll cur = prefix;
ll next = cur + 1;
ll cnt = 0;
while (cur <= n)
{
//总数不能比n还大
//比如n=1000 prefix=cur=15 next=16 15
//第一次cnt为15自己 cur=150 next=160 150-159
// cur=1500 next=1600 退出while
// 123 123456 当123增长到和123456一样长的时候 不能再加10的倍数 123456 然后就是加456
// 再比如456 和123456 456000的时候 无合法 直接退出
cnt += min(n + 1, next) - cur;
cur *= 10;
next *= 10;
}
return cnt;
}
int findKthNumber(int n, int k)
{
//前n个数字 字典序第k小
long p=1;//字典序最小的
long prefix=1;//前缀从1开始
while (p<k)
{
int tmp=getCnt(prefix,n);
if(p+tmp>k){
//如果说明加上之后超过k了 说明要求的答案就在这里面
prefix*=10;
p++;//跳过当前前缀
}else if(p+tmp<=k){
//说明第k个数不在这个前缀里面 则前缀需要扩大+1
prefix++;
p+=tmp;
}
}
return (int)prefix;
}
};