386. 字典序排数

386. 字典序排数

理解题目要求

题目要求我们生成从 1 到 n 的整数的字典序排列，并且要求：

• ​时间复杂度 O(n)​​：不能使用直接排序（通常指的是使用标准的排序算法（如快速排序、归并排序、堆排序等）对数据进行排序。这些排序算法的时间复杂度通常是 ​O(n log n)​，而题目要求的是 ​O(n)​​ 的时间复杂度，因此不能直接使用这些排序方法。）。
• ​空间复杂度 O(1)​​：不能使用额外的数组或数据结构存储中间结果。

字典序的定义

字典序（lexicographical order）是指按照字符串的字典顺序排列数字。例如：

• 1, 10, 100, 101, ..., 11, 110, ..., 2, 20, 200, ..., 3, 30, ...

关键观察

字典序可以看作是一个前缀树（Trie）​的深度优先遍历（DFS）顺序：

• 从 1 开始，尽可能往更深的位数扩展（即 ×10）。
• 如果无法继续扩展（比如 ×10 > n），则回溯到上一层（即 //10），并尝试 +1。

算法思路

1. ​初始化​：从 number = 1 开始。
2. ​尝试扩展（×10）​​：
   • 如果 number × 10 ≤ n，则 number × 10 是下一个字典序数字。
   • 否则，无法继续扩展，进入回溯阶段。
3. ​回溯（//10）并递增（+1）​​：
   • 如果 number % 10 == 9 或 number + 1 > n，说明当前层已经遍历完，需要回溯到上一层（number //= 10）。
   • 否则，number + 1 是下一个字典序数字。
4. ​终止条件​：已经收集 n 个数字。

示例

以 n = 13 为例：

1. 1 → 10（1×10）
2. 10 → 11（10 +1）
3. 11 → 12（11 +1）
4. 12 → 13（12 +1）
5. 13 → 2（13 +1 >13，回溯到 1，然后 1 +1=2）
6. 2 → 3（2 +1）
7. 3 → 4（3 +1）
   ... 直到收集 n 个数字。

代码实现

def lexicalOrder(n):res = []number = 1for _ in range(n):res.append(number)if number * 10 <= n:number *= 10else:while number % 10 == 9 or number + 1 > n:number //= 10number += 1return res

时间复杂度分析

• 每个数字 1..n 被处理一次，且每次操作是 O(1)，所以总时间复杂度是 ​O(n)​。
• 只用了常数空间存储 number 和 res（输出结果不计入空间复杂度），所以空间复杂度是 ​O(1)​。

为什么能保证 O(n) 时间？

• 每次操作要么 ×10（深度优先），要么 +1（广度优先），不会重复处理数字。
• 每个数字只会被访问一次，且操作是常数时间。

为什么能保证 O(1) 额外空间？

• 除了输出结果 res 外，只用了 number 这个变量，没有递归或额外数据结构。

总结

这个算法巧妙地利用了字典序的DFS遍历特性：

1. 优先往深层扩展（×10）。
2. 无法扩展时回溯并递增（//10 然后 +1）。
3. 整个过程不重复、不遗漏，严格 O(n) 时间、O(1) 空间。