话说作为一个菜鸡，我看到这个题第一反应是写了个trie树，后来发现数据size可能到10^9就放弃了。
之前对这种数位统计的问题都比较恐惧，这是一个需要非常细心的事情。硬着头皮写个题解也是为了让自己对题目更加理解。

算法1

(暴力枚举) $O(logn * logn)$

将整个过程分为两步：
- 1.构造一个函数count_prefix(prefix, n)，函数的功能是给定一个数字prefix,在[1，n]中找到以prefix为开头的数字的个数。
- 2.有个count_prefix后，findKthNumber如何迭代的求出符合条件的字典序第k个数字。

1.count_prefix函数：

给定prefix和n后，我们可以分情况讨论。

注意，由于题目限定，不存在prefix比n位数大的情况。

如果prefix的位数小于n. 我们用res来记录结果的个数，用k来代表n与prefix位数之差。则这个过程为：

i从0开始，判断是否小于k，如果小于，res+= 10 ^i.否则break;

循环结束后，已经计算完将prefix对齐到n的位数中，包含的结果的个数了。

最后看一下对齐之后结果需要加多少个。此时需要判断(n / power(10, k))与prefix的大小，记(n / power(10, k))为n_pre。

1.如果prefix > n_pre，则prefix*power(10,k) > n。可以直接返回结果了。  
2.如果prefix == n_pre,证明最后需要加(n - prefix * power(10, k) + 1)个数字.  
3.如果prefix < n_pre,证明最后需要加power(10, k)个数字.

我们通过一个例子来进行说明：
假设n = 123456, prefix = 123.

首先prefix的位数为3，n的位数为6.  
从1开始到123456中有多少以123开头的呢。 我们分位数来计算。

1.显然位数小于3的没有。  
2.位数等于3的有1个，为123  
3.位数等于4的有10个，为1230~1239  
4.位数等于5的有100个，12300~12399  
上面4步对应于我们的循环过程，即当prefix * power(10, i)的位数小于n的位数时，可以直接加上10^i个。  
5.位数等于6的有多少个呢。我们知道，以123开头位数等于6的数字有[123000,123999]共1000个，在这1000个数字中哪些是小于等于n的呢。
应该是[123000,123456]共计 123456-123000 + 1个。  
因此最后的总数就是把1-5步所有结果相加起来的数字。  
我们观察一下这种情况，此时(n_pre = 123),且 n_pre == prefix.对应我们的情况2.

让我们把prefix替换为122试一下:

假设n = 123456, prefix = 122.

首先prefix的位数为3，n的位数为6.  
从1开始到123456中有多少以122开头的呢。 我们分位数来计算。

1.显然位数小于3的没有。  
2.位数等于3的有1个，为122  
3.位数等于4的有10个，为1220~1229  
4.位数等于5的有100个，12200~12299  
前面几步与情况1相同。

5.位数等于6的有多少个呢。  
此时以122开头位数等于6的数字有[122000,122999]共1000个。而这1000个数字全部小于123456，因此结果直接加1000就可以。

最后把prefix替换为124试一下:

假设n = 123456, prefix = 124.

首先prefix的位数为3，n的位数为6.  
从1开始到123456中有多少以122开头的呢。 我们分位数来计算。

1.显然位数小于3的没有。  
2.位数等于3的有1个，为122  
3.位数等于4的有10个，为1220~1229  
4.位数等于5的有100个，12200~12299  
前面几步与情况1、2相同。

5.位数等于6的有多少个呢。  
此时以124开头位数等于6的数字有[124000,124999]共1000个。而这1000个数字全部大于123456，因此一个也不加。

让我们总结一下。
- 如果n_prefix> prefix，证明prefix拉到与n相同的位数( power(10, k))后，均小于n。直接加power(10, k).
- 如果n_prefix == prefix，证明prefix拉到与n相同的位数( power(10, k))后，有若干个数字小于等于n，此时结果为n-prefix * power(10, k) + 1.
- 如果n_prefix < prefix,证明证明prefix拉到与n相同的位数(* power(10, k))后，均大于n。因此一个数也不加

2.findKthNumber函数

有了count_prefix函数后，我们可以通过枚举来确定第k个数是多少。

首先我们的k从1开始，也就是当k为1时，我们可以直接确定当前的前缀就是剩下数字里面的一个数。

让我们从prefix = 1开始，调用count_prefix(prefix, n)得到[1,n]中有多少的数字以prefix为前缀，结果为cnt。那么结果可能有三种。
1. cnt < k。此时代表以prefix为开头的数字的个数小于k个，那么第k个数字必然不是以prefix开头的。就要从以prefix+1为开头的数字中找k-cnt个。

1. cnt == k
   此时代表第k个数必定以prefix开头，但第k个数不是prefix。
   为什么呢？因为我们的结束条件是k == 1。在进入循环判定的时候k肯定是大于1的。
   因此当cnk==k时，证明第k个数字以prefix为开头，但不是prefix。我们就可以深入下去，让prefix从prefix * 10开始尝试了。注意此时要将k-1。
   把当前的prefix排除进去。

2. cnt > k
   此时代表第k个数必定以prefix开头，但第k个数不是prefix。
   与cnt ==k情况相同，因此可以合并。

我们以一个例子来进行说明。

n = 100, k = 30.
prefix = 1

1.  首先判断k>1.因此进入判定循环:  
    count_prefix(1, 100)为12(1,10~19, 100);  
    12 < 30，说明第k个数不在1开头的数字里。从2开头的数字开始找第(k-12=18)个. 
    此时prefix == 2, k = 18

2.  count_prefix(2, 100)为11(2,20~29);  
    11 < 18,说明第k个数不在2开头的数字里。从2开头的数字开始找第(k-12-11=7)个.
    此时prefix == 2, k = 7

3.  count_prefix(3, 100)为11(3,30~39);  
    11 > 7,说明第k个数在以3为开头的数组里，可能是30/31/32...，但肯定不是3。  
    因此我们要从30开始找起。这时不是找第7个了，而是找第6个，因为把3排除了。
    此时prefix == 30, k == 6

4.  count_prefix(30, 100)为1(30);
    1 < 6, 说明第k个数不在30开头的数字里。从31开头的数字开始找第(6 - 1=5)个.
    此时prefix == 31, k = 5

5.  count_prefix(31, 100)为1(31);
    1 < 5, 说明第k个数不在31开头的数字里。从32开头的数字开始找第(5 - 1=4)个.
    此时prefix == 32, k = 4

6.  count_prefix(32, 100)为1(32);

    1 < 4, 说明第k个数不在32开头的数字里。从33开头的数字开始找第(4 - 1=3)个.
    此时prefix == 33, k = 3

6.  count_prefix(33, 100)为1(33);

    1 < 3, 说明第k个数不在33开头的数字里。从33开头的数字开始找第(3 - 1=2)个.
    此时prefix == 34, k = 2

7.  count_prefix(34, 100)为1(34);

    1 < 2, 说明第k个数不在34开头的数字里。从34开头的数字开始找第(2 - 1=1)个.
    此时prefix == 35, k = 1
8.此时k不在满足 k> 1的条件了，当前的prefix就是结果。因此findKthNumber函数(100, 30)就是35.

然后让我们用代码来实现一个我们的思路

C++ 代码

int count_prefix(int prefix, int n) {//给定数字n，求出1~n中以prefix为前缀的数字
    long long p = 1;                 //记录当前有多少个数字小于n
    int res = 0;                     //返回结果
    string source = to_string(prefix);     //将num，n 转换为字符串比较容易计算相差的位数。
    string target = to_string(n);
    int k = target.size() - source.size();  //及prefix后面补多少个0达到和n一样的位数。
    for(int i = 0; i < k; i++){
        res += p;
        p *= 10;
    }
    string n_prefix = target.substr(0, source.size()); //将n拉倒与prefix一样的位数，得到n_pre
    if(n_prefix > source)              //对应条件3，此时的p为power(10, k)
        res += p;
    else if(n_prefix == source)        //对应条件2，此时的p为power(10, k),prefix * p拉到和n一样的位数。
        res += n - prefix * p + 1;
    return res;                       //条件1不改变结果，因此可以再判断中略去。直接返回就好了



}

int findKthNumber(int n, int k) {
    int prefix = 1;                         //prefix从1开始
    while(k > 1){                           //如果k ==1，则prefix就是我们要找的数
        int cnt = count_prefix(prefix, n);  //计算以prefix开头的数字的个数。
        if(cnt < k){                        //对应条件1。
            k -= cnt;
            prefix++;
        }
        else{                               //对应条件2、3。
            k--;
            prefix *= 10;
        }
    }
    return prefix;
}

时间复杂度

count_prefix函数的复杂度为logn(遍历n数字的长度).
findKthNumber(遍历n数字的长度).
整体的复杂度为logn * log n;