440. 字典序的第K小数字

440. 字典序的第K小数字

十叉树

typedef long long ll;
class Solution {
public:
    int getcount(int prefix, ll n){
        int count=0;
        ll cur=prefix;
        ll nxt=prefix+1;
        while(cur<=n){
            count += min(n+1, nxt)-cur;
            cur*=10;
            nxt*=10;
        }
        return count;
    }
    int findKthNumber(int n, int k) {
        int p=1, prefix=1;
        while(p<k){
            int count=getcount(prefix,n);
            if(p+count>k){
                prefix*=10;
                p++;
            }else{
                prefix++;
                p+=count;
            }
        }
        return prefix;
    }
};