点击获取AI摘要

440. 字典序的第K小数字 H

给定整数 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 <= 10⁹

问题分析

题目要求在区间 $[1, n]$ 中，找到按字典序排序后第 $k$ 小的数字。若将所有数字看作字符串并按字典序排列，实际等价于在一个“字典树”（Trie）结构上做先序遍历，找到第 $k$ 个节点对应的数字。具体分析如下：

字典序与Trie 树
- 数字 $1,2,\dots,9$ 作为第一层节点；以“前缀”为思路，若当前节点是 $x$ ，则其子节点为 $10x,\,10x+1,\,\dots,\,10x+9$ （只要 $\le n$ ）。
- 字典序遍历等价于对这棵树做“先序遍历”（先访问节点本身，再遍历其子树），返回顺序即为字典序。
前缀下节点计数
- 对于任意前缀 $p$ ，需要统计以 $p$ 为前缀的所有数字在 $[1,n]$ 范围内的个数。记为 $\text{count}(p,n)$ 。
- 计算思路：令
  $\text{cur} = p,\quad \text{nxt} = p+1,\quad \text{cnt} = 0.$
  在每一轮，将当前层中所有以 $\text{cur}$ 开头且不超过 $n$ 的数字数量累加到 $\text{cnt}$ ：
  $\text{cnt} \;+\!=\; \min(\text{nxt},\,n+1)\;-\;\text{cur}.$
  然后向下一层扩展：
  $\text{cur} \;\gets\; \text{cur} \times 10,\quad \text{nxt} \;\gets\; \text{nxt} \times 10,$
  直至 $\text{cur} > n$ 为止。
贪心移动思路
- 从当前前缀 $\text{curr}$ 出发，假设已访问了 $1$ （即将 $k \leftarrow k - 1$ ）。
- 在循环中，每步计算 $\text{nodes} = \text{count}(\text{curr},\,n)$ $nodes = count (curr, n)$ ：
  1. 若 $\text{nodes} \le k$ ，说明第 $k$ 小不在以 $\text{curr}$ 为前缀的子树中，可“跳过”整棵子树：
    $k \leftarrow k - \text{nodes},\quad \text{curr} \leftarrow \text{curr} + 1.$
  2. 否则，第 $k$ 小就在该子树中，此时先访问 $\text{curr}$ 本身（ $k \leftarrow k-1$ ），再进入下一层：
    $\text{curr} \leftarrow \text{curr} \times 10.$
- 重复上述过程，直到 $k = 0$ ，此时 $\text{curr}$ 即为答案。

算法思路

初始化

1 2	curr = 1 k = k - 1 // 因为我们把数字 1 当作第一个访问

定义前缀计数函数

count(prefix, n):
    cnt  = 0
    cur  = prefix
    nxt  = prefix + 1
    while cur <= n:
        cnt += min(nxt, n+1) - cur
        cur *= 10
        nxt *= 10
    return cnt

主循环

while k > 0:
    nodes = count(curr, n)
    if nodes <= k:
        // 第 k 小不在以 curr 为前缀的子树
        k    = k - nodes
        curr = curr + 1
    else:
        // 第 k 小在以 curr 为前缀的子树
        k    = k - 1   // 访问 curr 本身
        curr = curr * 10
return curr

最终，curr 即为区间 $[1,n]$ 中按字典序排列后的第 $k$ 小数字。

时间复杂度

计算 $\text{count}(p,n)$ 需要不断把前缀乘以 10，层数最多为 $\lfloor \log_{10} n \rfloor + 1$ 轮，故单次 $\text{count}$ 调用开销为 $O(\log n)$ 。
在主循环中，每次循环要么做一次 $+!1$ 操作（兄弟前缀），要么做一次 $\times 10$ 操作（进入子树）。最坏情况下循环次数为 $O(\log n + \text{跳过次数})$ 。虽然 $k \le n$ ，但当 $\text{count}(curr,n)$ 很大时，一次可跳过大量节点，因此实际循环次数远小于 $n$ 。
综合来看，主循环中每次都要调用一次 $\text{count}$ ，复杂度近似为

$O\bigl(\text{循环次数} \times \log n\bigr) \approx O\bigl((\log n)^2\bigr).$

代码分解

主函数 findKthNumber(n, k)

作用：初始化参数，循环寻址第 $k$ 小数字。
核心变量：
- curr：当前前缀（已定位到树中的某个节点）。
- k：剩余需要定位的偏移量。

辅助函数 count(prefix, n)

作用：计算当前前缀 prefix 下，在 $[1,n]$ 范围内共有多少个数字。
逻辑：
- cur = prefix, nxt = prefix + 1, cnt = 0
- 每轮累加 $\min(nxt,,n+1) - cur$ ，然后 cur *= 10, nxt *= 10，直到 cur > n。
- 返回累计的 cnt。

跳过与进入逻辑

若 count(curr,n) <= k：
- k -= count(curr,n)，跳过整个子树；
- curr += 1，移动到下一个兄弟前缀。
否则：
- k -= 1，访问当前前缀节点本身；
- curr *= 10，进入该前缀的第一个子节点。

循环终止

当 k == 0 时，curr 即为答案，直接返回。

代码实现

class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        # 将 1 看作第一个访问，故 k 减 1
        curr = 1
        k -= 1

        # 辅助函数：统计在 [1, n] 中，以 prefix 为前缀的数字总数
        def count(prefix: int, n: int) -> int:
            cnt = 0
            cur = prefix
            nxt = prefix + 1
            # 向下遍历每一层，直到前缀超出 n
            while cur <= n:
                cnt += min(nxt, n + 1) - cur
                cur *= 10
                nxt *= 10
            return cnt

        # 不断贪心地“跳过”或“深入”子树，直到找到第 k 小
        while k > 0:
            nodes = count(curr, n)
            if nodes <= k:
                # 跳过以 curr 为前缀的整棵子树
                k -= nodes
                curr += 1
            else:
                # 第 k 小在以 curr 为前缀的子树里
                k -= 1      # 先访问 curr 本身
                curr *= 10  # 进入下一层第一个子节点

        return curr