当前位置：首页 > news >正文

386. 字典序排数

news 2025/12/16 16:46:38

这个问题是经典的 "字典序排序"（Lexicographical Order）问题，要求按字典序输出 [1, n] 的数字，并且要求 O(n) 时间 和 O(1) 额外空间（不包括输出占用的空间）。

思路分析

字典序比较规则：

比较数字的字符串形式，例如 10 在 2 之前，因为 "10" < "2" 按字符串比较。

直接排序会超过 O(n) 时间，所以需要用 DFS 风格的生成方法 来按字典序遍历。

核心思想：

从 1 到 9 开始，对每个数字 curr：
- 先输出 curr
- 然后递归地（或迭代地）处理 curr * 10 到 curr * 10 + 9 的数字，只要它们 <= n
这实际上是在遍历一个 十叉树 的先序遍历。

算法步骤（迭代 / 模拟 DFS）

我们可以用迭代来避免递归栈空间，实现 O(1) 额外空间（除了输出列表）。

初始化 curr = 1
循环直到处理完所有数字：
- 把 curr 加入结果
- 如果 curr * 10 <= n，则进入下一层（更长的数字前缀）
- 否则：
  - 如果 curr % 10 == 9 或 curr + 1 > n，则回溯到上一层（curr = curr / 10）
  - 否则 curr++
直到 curr == 1 且需要回溯时结束（实际可判断结果数量达到 n 个停止）

代码实现

/*** @param {number} n* @return {number[]}*/
var lexicalOrder = function(n) {const result = [];let curr = 1;for (let i = 0; i < n; i++) {result.push(curr);if (curr * 10 <= n) {// 进入下一层：curr -> curr * 10curr *= 10;} else {// 到达该层末尾或 n 的限制if (curr >= n) {curr = Math.floor(curr / 10);}curr += 1;// 跳过末尾0，直接进位while (curr % 10 === 0) {curr = Math.floor(curr / 10);}}}return result;
};

更清晰的迭代实现（推荐）

var lexicalOrder = function(n) {const result = [];let num = 1;for (let i = 0; i < n; i++) {result.push(num);if (num * 10 <= n) {num *= 10; // 深度优先：先走最左路径} else {// 回溯：如果到了末尾或超出 n，则回到上层if (num >= n) {num = Math.floor(num / 10);}num += 1;// 处理进位产生的末尾0while (num % 10 === 0) {num = Math.floor(num / 10);}}}return result;
};

示例

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

执行过程（简略）：

1 → 10 → 11 → 12 → 13 → 回溯到 1 → 2 → 3 ... → 9

复杂度分析

时间复杂度：O(n)，每个数字恰好处理一次。
空间复杂度：O(1) 额外空间（不包括存储结果的数组）。

好的，我来详细解释 DFS 风格的生成方法 来解决字典序排序问题。

核心思想

把数字 1~n 看作一个 十叉树：

根节点是空字符串
每个节点的子节点是在末尾添加 0~9
按 先序遍历 这棵树，就得到字典序

例如 n=20：

        (root)/  |  \1   2   3...9/|\10 11 12...19/100... (但>20，停止)

DFS 递归实现

var lexicalOrder = function(n) {const result = [];function dfs(current) {if (current > n) return;if (current > 0) {result.push(current);}// 对当前数字，尝试添加 0~9for (let i = 0; i <= 9; i++) {if (current === 0 && i === 0) continue; // 避免 "0"const next = current * 10 + i;if (next > n) break; // 提前终止dfs(next);}}dfs(0); // 从0开始，但跳过0本身return result;
};

问题：递归会使用 O(log n) 的栈空间，不完全符合 O(1) 空间要求。

迭代 DFS（O(1) 空间）

模拟 DFS 的栈行为，但不实际用栈：

var lexicalOrder = function(n) {const result = [];let curr = 1;for (let i = 0; i < n; i++) {result.push(curr);if (curr * 10 <= n) {// DFS 深入：往左子树走 (curr * 10)curr *= 10;} else {// 到达当前分支末尾，需要回溯if (curr >= n) {curr = Math.floor(curr / 10);}curr += 1;// 跳过末尾的0，比如 19 -> 20 应该变成 2while (curr % 10 === 0) {curr = Math.floor(curr / 10);}}}return result;
};

DFS 遍历的直观理解

以 n=13 为例，DFS 遍历路径：

1 → 10 → 11 → 12 → 13 → 回溯 → 2 → 3 → 4 → ... → 9

DFS 规则：

如果能 ×10 还在 n 内，就 ×10（往深层走）
否则 +1（同层下一个）
如果 +1 后超过 n 或进位了，就回溯到上层

带详细注释的版本

var lexicalOrder = function(n) {const result = [];let num = 1;for (let i = 0; i < n; i++) {result.push(num);// 1. 优先往深层走：num -> num*10if (num * 10 <= n) {num *= 10;} else {// 2. 当前层遍历完毕或超出n，需要调整if (num >= n) {// 如果当前数已经>=n，回溯到上一层num = Math.floor(num / 10);}num += 1;// 3. 处理进位：比如 199 -> 200 应该变成 2while (num % 10 === 0) {num = Math.floor(num / 10);}}}return result;
};