LeetCode 440题 “K-th Smallest in Lexicographical Order” 是一个中等难度的题目，主要考察的是字典序（lexicographical order）和数字的排列组合。

题目描述

给定整数 n 和 k，找到从 1 到 n 的所有整数按字典序排列后的第 k 个数。

字典序排列是指将数字视为字符串，按照字典顺序排列。例如，对于 n = 13，字典序排列为 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]。

解法思路

这个问题可以通过递归和数学的方法来解决。核心思想是利用字典树的性质，逐步缩小范围，找到第 k 个数。

步骤：

1. 初始化：从根节点 1 开始。
2. 计算子节点数量：对于当前节点 curr，计算从 curr 到 curr + 1 之间的所有子节点的数量。
3. 比较 k 和子节点数量：
   • 如果 k 小于等于子节点数量，说明第 k 个数在当前节点的子树中，更新 curr 为 curr * 10 并继续搜索。
   • 如果 k 大于子节点数量，说明第 k 个数不在当前节点的子树中，更新 curr 为 curr + 1 并减去当前子树节点的数量，继续搜索。

关键函数：

• countSteps(curr, n)：计算从 curr 到 curr + 1 之间的所有子节点的数量。

代码实现

class Solution: def findKthNumber(self, n, k): curr = 1 k -= 1 # 因为从1开始计数，所以k减1

    while k > 0:
        steps = self.countSteps(curr, n)
        if steps <= k:
            # 第k个数不在当前子树中
            curr += 1
            k -= steps
        else:
            # 第k个数在当前子树中
            curr *= 10
            k -= 1

    return curr

def countSteps(self, curr, n):
    steps = 0
    first = curr
    last = curr

    while first <= n:
        steps += min(n + 1, last + 1) - first
        first *= 10
        last = last * 10 + 9

    return steps

sol = Solution() print(sol.findKthNumber(13, 2)) # 输出: 10 print(sol.findKthNumber(13, 5)) # 输出: 13

解释

1. 初始化：curr 从 1 开始，k 减 1 是因为从 1 开始计数。
2. 循环：当 k 大于 时，计算从 curr 到 curr + 1 之间的子节点数量。
3. 子节点数量计算：
   • first 和 last 分别表示当前层的起始和结束节点。
   • 通过循环扩展 first 和 last 到下一层，累加每层的节点数量。
4. 更新 curr 和 k：
   • 如果 k 大于子节点数量，说明第 k 个数不在当前子树中，curr 增加 1，k 减去当前子树节点数量。
   • 如果 k 小于等于子节点数量，说明第 k 个数在当前子树中，curr 扩展到下一层（curr * 10），k 减去 1（因为进入下一层）。

通过这种方法，逐步缩小范围，最终找到第 k 个数。

希望这个详细的解释和代码实现能帮助你理解并解决这个题目！如果有任何进一步的问题，欢迎继续提问。