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

发布于 2022-03-25  314 次阅读


原题链接


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等同的前缀uprefix的大小关系,进一步分情况讨论(举个🌰,当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;
  }
};

愿风指引你的道路,愿你的刀刃永远锋利。