[leetcode440]字典序的第k小数字

原题链接

---

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;
  }
};