从字典到数字的第K个数字，从1到N

Question

给定一个整数N，找到从1到N的按字典顺序排序的数字数组中排名第k的第k个字符。

例如：N = 12

按字典顺序排序的数字是：[1、10、11、12、2、3、4、5、6、7、8、9]

如果K = 4，则程序应返回：12。

程序的复杂度应为O（logN）。

出于解释目的而生成该数组，但不将其作为输入提供。数组的生成和排序将花费Nlog（N）时间，因此无法达到目的。

我最近在面试过程中遇到了这个问题。无法在给定的时间复杂度下找到解决方案，因此寻求帮助

谢谢！！

Answer 1

假设 N = 13000，K = 12031。当分配为最左边时，从 1 到 9 的每个数字得到：

                                      total
1 single digit number 9 * 1              9
10 two-digit numbers  9 * 10            99
100 three-digit numbers 9 * 100        999
1000 four-digit numbers 9 * 1000      9999
10000 five-digit numbers      --->  here we have to start examining

                                             Total
                                             ----
1 gets 13000 - 8 * (1 + 10 + 100 + 1000)  =  4112 of them
2 gets 1111                                  5223
3 gets 1111                                  6334
4 gets 1111                                  7445
5 gets 1111                                  8556
6 gets 1111                                  9667
7 gets 1111                                  10778
8 gets 1111                                  11889
9 gets 1111 ----> answer is somewhere here 

回答：9xxx。现在是第二个数字。对于每个以一个或多个零结尾的数字，我们必须计算具有等效前缀的所有较低数字。

3 numbers with zero or nothing before 9000   11892
9 90 900

100 + 9 numbers with 90xx
9000 9001 9002.., but also 901 902..         12001

回答：91xx。第三位数字。

2 numbers with zero or nothing before 9100
91 910                                       12003

10 four-digit numbers with 0 as third digit
9100 9101 9102..                             12013

1 number with zero or nothing before 9110
911                                          12014

10 numbers with 1 as third digit
9110 9111 9112..                             12024

1 number with zero or nothing before 9120
912                                          12025

+ 6

回答：9126