点击获取AI摘要

386. 字典序排数 M

给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。

你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。

示例 1：

输入：n = 13
输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]

示例 2：

输入：n = 2
输出：[1,2]

提示：

1 <= n <= 5 * 10⁴

问题分析

要求按字典序返回范围 [1, n] 内所有整数，相当于将所有数字看作字符串（“1”、“2”、“10”、“11”…），然后按字符串顺序输出。如果直接将所有数字转为字符串后排序，时间复杂度将会达到 $O(n \log n)$ ，且需要额外 $O(n)$ 空间来保存所有字符串。题目要求时间复杂度为 $O(n)$ 且只能使用 $O(1)$ 额外空间（不计返回结果本身）。因此，需要设计一种在线（在线性时间）地“遍历”数字的方法，而不借助常规排序或额外存储全部字符串。

本质上可将 [1, n] 视作一棵“十叉树”（Trie）：

树的根节点对应空（不输出任何数字），根下有 1 到 9 共 9 个子节点，分别对应数字 1、2、…、9。
每个节点 $x$ （数值）下又有最多 10 个子节点： $x0,\;x1,\;\dots,\;x9$ ，其中仅保留不超过 $n$ 的那些。例如，若 $x = 1$ ，其子节点为 10、11、12…19 中不大于 $n$ 的数字。
对这棵树进行先序遍历（Pre-order），遍历顺序恰好就是字典序。例如 $n=13$ 时，先序遍历顺序为：

得到的序列即为 $[1,\,10,\,11,\,12,\,13,\,2,\,3,\,4,\,5,\,6,\,7,\,8,\,9]$ 。

由于 $n$ 最大为 $5\times10^4$ ，不算特别大，但我们仍不能显式构建整棵树。需要设计一种常数空间、线性时间地模拟先序遍历的过程。

算法思路

设一个变量 curr 用来表示“当前要输出的数字”，初始设为 $1$ 。每次输出 curr 后，尝试移动到“下一个字典序”位置，遵循以下三步优先级：

深入子节点：如果 $curr \times 10 \le n$ ，则令

$curr = curr \times 10.$

此时相当于先序遍历中的“向左下走”，遍历同前缀最左侧的子节点。
右兄弟：否则，如果 $curr \bmod 10 \neq 9$ 且 $curr + 1 \le n$ ，则令

$curr = curr + 1.$

这样做相当于先序遍历中“当前节点访问完毕后，去右兄弟”。
回溯到父节点并向上层兄弟：若上述两步都无法执行（要么尾数为 9，要么 $curr+1>n$ ），则说明当前节点已经到该层最右侧或下层节点超出范围，需要一路“回溯到父节点”：
1
2
3
while curr % 10 == 9 or curr + 1 > n:
curr //= 10
curr += 1
这段逻辑对应先序遍历中的“回到父节点，继续访问父节点的右兄弟”。

整个过程实际运行了 $n$ 步，每一步中的乘、加、除操作都为常数时间，且只使用了若干整型变量，不申请额外数组或栈。

时间复杂度

对于每个 $1 \le i \le n$ ，都会恰好执行一次循环并向结果列表加入一个数，循环体内的所有操作（乘以 10、判断、加 1、整除）均为 $O(1)$ 。共 $n$ 次迭代，因此总时间复杂度为

$O(n).$

额外空间仅使用了常数个整型变量（例如 curr、循环索引等），不计返回的结果列表，故空间复杂度为

$O(1).$

代码分解

初始化

创建空列表 result 用于存放最终的字典序序列。
设置整数变量 curr = 1，表示当前输出的数字。

主循环（执行 $n$ 次）
对于第 $i$ 次迭代（ $i=1,\dots,n$ ）：

将当前 curr 添加到 result 中。
若 $curr \times 10 \le n$ ，则令 curr = curr * 10；跳转到“更深层”。
否则，若 curr % 10 != 9 且 curr + 1 <= n，则令 curr += 1；跳转到“右兄弟”。
否则，执行：
1
2
3
while curr % 10 == 9 or curr + 1 > n:
curr //= 10
curr += 1
该循环确保一路向上回溯到某个还可 +1 的节点，然后加 1，跳转到该层右兄弟。

返回结果
循环结束后，result 中正好按字典序保存了 1 到 $n$ 的所有整数。

代码实现

class Solution:
    def lexicalOrder(self, n: int) -> List[int]:

        # 结果列表
        result = []
        # curr 表示当前要输出的数字，初始为 1
        curr = 1

        for _ in range(n):
            result.append(curr)
            # 尝试“往下一层”（乘 10）
            if curr * 10 <= n:
                curr *= 10
            else:
                # 不能向下，则尝试“向右兄弟”（+1），但要保证不越界且尾数不为 9
                if curr % 10 != 9 and curr + 1 <= n:
                    curr += 1
                else:
                    # 如果当前尾数为 9 或 +1 会越界，则回溯到父节点
                    while curr % 10 == 9 or curr + 1 > n:
                        curr //= 10
                    curr += 1

        return result