标签: 字典树
难度: Hard
给定整数 n 和 k，返回 [1, n] 中字典序第 k 小的数字。
示例 1:
输入: n = 13, k = 2 输出: 10 解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。
示例 2:
输入: n = 1, k = 1 输出: 1
提示:
1 <= k <= n <= 109
Submission
运行时间: 24 ms
内存: 16.0 MB
class Solution:
def findKthNumber(self, n: int, k: int) -> int:
res = 1
k -= 1
while k > 0:
cnt = 0
interval = [res, res+1]
while interval[0] <= n:
cnt += min(n+1, interval[1]) - interval[0]
interval = [10*interval[0], 10*interval[1]]
if k >= cnt:
res += 1
k -= cnt
else:
res *= 10
k -= 1
return res
Explain
这个题解使用了一种巧妙的方法来找到字典序第k小的数字。主要思路是：从1开始，通过计算当前前缀下所有数字的个数，判断第k个数字是否在当前前缀下。如果在当前前缀下，则第k个数字的第一位就是当前前缀；如果不在，则将前缀加1，继续查找下一个前缀。重复这个过程，直到找到第k个数字。
时间复杂度: O((log n)^2)
空间复杂度: O(1)
class Solution:
def findKthNumber(self, n: int, k: int) -> int:
res = 1
k -= 1
while k > 0:
cnt = 0
interval = [res, res+1]
while interval[0] <= n:
# 计算当前前缀下的数字个数
cnt += min(n+1, interval[1]) - interval[0]
# 将区间扩大10倍，向下遍历10叉树
interval = [10*interval[0], 10*interval[1]]
if k >= cnt:
# 第k个数字不在当前前缀下，前缀加1
res += 1
k -= cnt
else:
# 第k个数字在当前前缀下，第一位确定为当前前缀
res *= 10
k -= 1
return res
Explore
在这个解法中，'前缀'指的是数字序列中的起始部分，这可以是一个或多个数字的组合。例如，如果前缀是'123'，那么以这个前缀开头的数字包括123, 1230, 1231, ... 等等。在字典序问题中，前缀决定了数字的排列顺序，所有以同一前缀开始的数字会在字典序中连续出现，且按照从小到大的顺序排列。
这种计算方法是为了能够高效地估算出在指定前缀下的数字个数。区间 [interval[0], interval[1]) 表示以当前前缀开始直到下一个前缀开始之前的所有可能数字。例如，前缀为1的区间初值是[1, 2)，代表数字1到1结束之前的所有数字。在每次迭代中，区间扩大10倍，例如[10, 20)，[100, 200)，这样做是因为每个数字都可以扩展出10个更长的数字（通过在末尾添加0到9），从而形成一个完整的10叉树结构，该结构帮助我们快速计算出在当前前缀下所有可能的数字个数。
当确定k不在当前前缀下时，意味着我们需要跳过当前前缀下的所有数字，寻找下一个可能的前缀。将前缀加1是逻辑上的下一步，因为在字典序中，下一个可能的较大前缀正是当前前缀加1（例如从'1'变到'2'）。这样做可以有效地将搜索范围缩小到下一个前缀的字典序区域，避免不必要的搜索，从而提高查找效率。
当确定第k个数字在当前前缀下时，将结果乘以10是因为我们需要进一步细化搜索，探索以当前前缀作为更高位数的新前缀的更具体的数字。例如，如果当前前缀是1，下一步我们需要探索10, 11, 12, ... 等等。将k减去1是因为我们已经确定了一个数字的位置（当前前缀自身），接下来需要在新的更具体的前缀下找到第k-1个数字。这种方法保持了算法的递归性质，使我们能够逐步逼近目标数字。