从1到N按字典顺序排序的数字中的第K个数字

Question

给定一个整数N，从1到N的字典序排序的数字数组中找到第k个排名的数字。 例如：N = 12 字典序排序的数字是：[1, 10, 11, 12, 2, 3, 4, 5, 6, 7, 8, 9] 如果K=4，则程序应返回：12。 程序的复杂度应为O(logN)。 该数组是为了解释而生成的，不作为输入提供。生成数组和排序将花费Nlog(N)的时间，因此打败了目的。 我最近在面试过程中遇到了这个问题。在规定的时间复杂度内无法找出解决方案，因此请求帮助。 谢谢！

- Souvik Karmakar

---

这是一种使用词典序作为全序的二分查找算法。 - Reblochon Masque

@ReblochonMasque 我不明白 - 你会如何制定这个二分法？（请记住，我们没有实际的列表，只有N和K） - גלעד ברקן

抱歉，我想我误读了问题。您可以使用最小堆来检索第k个值。 - Reblochon Masque

@ReblochonMasque 我还是不太明白 :) 如果你只给定两个整数N和K，并且被要求在O(log N)时间内提供从1到N的所有按字典顺序排序的数字中的第K个数字，你会如何使用堆？ - גלעד ברקן

哦，我明白了... 我确实误解了问题... - Reblochon Masque

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。现在看第二个数字。对于每个以一个或多个0结尾的数字，我们必须计算所有具有相同前缀的较低数字。

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

- גלעד ברקן