LeetCode 386. 字典序排数

约 5 分钟
文章信息 12 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 字节跳动 微软 阿里巴巴 猿辅导 百度 拼多多 虾皮
标签
深度优先搜索 字典树
目录

题目描述

✅ 386. 字典序排数

题意分析

给定整数 n，要求把 1 到 n 这 n 个整数按字典序（也就是当成字符串比较大小的顺序）排好返回。例如 n = 13 的答案是 [1,10,11,12,13,2,3,4,5,6,7,8,9]——10 排在 2 前面，因为字符串 "10" 的首字符 '1' 小于 '2'。

最重要的约束信号写在进阶要求里：必须在 $O(n)$ 时间内完成，且除返回值外只能使用 $O(1)$ 的额外空间。这一条直接封死了「生成全部数字再排序」的常规路线——排序至少 $O(n \log n)$，而按字符串排序还要额外的 $O(n)$ 空间存转换结果。换句话说，题目要的不是「排序」，而是「按字典序直接把数字一个个生成出来」。

观察一下答案的形状：1 之后紧跟着的是以 1 为前缀的所有数（10、11、12、13），走完这一支才轮到 2。字典序的本质是先比前缀，前缀相同则短的在前，所以这个顺序正是「1 到 n 的数字按前缀关系组织成一棵十叉树后的先序遍历」：根有 1 到 9 共九个子节点，任意节点 x 的子节点是 $10x$ 到 $10x + 9$，超过 n 的节点不存在。

边界上要注意：n 最小是 1，此时答案就是 [1]；节点的孩子可能全都越界（比如 n = 13 时 2 的孩子 20 已经超了），此时要能正确地退回到兄弟；数字 0 不在结果里，它只能作为其他数字的非首位数字出现，所以遍历永远从 1 起步、根节点的孩子从 1 而不是 0 开始。

解法：十叉树先序迭代

核心思路

把数字看成一棵隐式十叉树：根节点下面是 1 到 9，节点 x 的孩子依次是 10x 到 10x + 9。这棵树的先序遍历恰好就是字典序，因为要先输出较短前缀 x，再输出所有以 x 开头的数字，最后才轮到它的下一个兄弟。

因此不需要把整数转成字符串后排序，只要用一个变量 cur 模拟先序遍历：

  • 若 cur * 10 <= n，优先下探到第一个孩子 cur * 10；
  • 否则尝试右移到兄弟 cur + 1；若末位已经是 9，或兄弟超过 n，就不断执行 cur /= 10 回到祖先，直到存在下一个兄弟。

循环不变量是：每轮开始时，cur 都是字典序中下一个尚未输出的合法数字。下探对应先序遍历进入子树，连续回退后右移对应离开已遍历完的子树，因此状态转移不会漏数或重复。合法数字一共恰好有 n 个，循环固定执行 n 次即可；最后一轮之后的 cur 值无需再使用。

解题步骤

  1. 初始化 cur = 1，结果数组预留 n 个位置。
  2. 每轮先把 cur 加入答案。
  3. 若 cur <= n / 10，说明第一个孩子没有越界，令 cur *= 10。
  4. 否则，只要 cur 的末位为 9，或 cur + 1 > n，就令 cur /= 10 连续回退。
  5. 回退结束后执行 cur++，进入当前层的下一个兄弟；重复以上过程共 n 轮。

例如 n = 13：1 先下探到 10，随后右移到 11、12、13；13 没有合法孩子或兄弟，于是回退到 1 再右移到 2，最后依次得到 3 到 9。结果为 [1,10,11,12,13,2,3,4,5,6,7,8,9]。

代码实现

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> res = new ArrayList<>(n);
        int cur = 1;
        for (int i = 0; i < n; i++) {
            res.add(cur);
            if (cur <= n / 10) {
                cur *= 10;
            } else {
                while (cur % 10 == 9 || cur + 1 > n) {
                    cur /= 10;
                }
                cur++;
            }
        }
        return res;
    }
}

func lexicalOrder(n int) []int {
    res := make([]int, 0, n)
    cur := 1
    for i := 0; i < n; i++ {
        res = append(res, cur)
        if cur <= n/10 {
            cur *= 10
        } else {
            for cur%10 == 9 || cur+1 > n {
                cur /= 10
            }
            cur++
        }
    }
    return res
}

复杂度分析

  • 时间复杂度：$O(n)$。每个数字输出一次；所有下探与回退可以摊还到整次遍历中，总移动次数与节点数同阶。
  • 空间复杂度：$O(1)$。不计返回结果，只使用常数个变量，没有递归栈和字符串数组。

关键点总结

  • 关键建模：数字前缀构成隐式十叉树，字典序就是先序遍历。
  • 三个算术动作足以代替建树：cur * 10 下探、cur + 1 右移、cur / 10 回退。
  • 必须先下探，再考虑兄弟；这正是「前缀相同的数字连续出现」的原因。
  • 回退必须使用 while，因为一棵子树结束时可能连续退出多层。
  • 递归 DFS 思路也正确，但需要 $O(\log n)$ 的调用栈；迭代模拟才能满足题目的 $O(1)$ 额外空间要求。

易错点总结

  • 只判断 cur % 10 == 9，会在 n = 13 时从 13 错走到 14；还必须判断 cur + 1 > n。
  • 只判断 cur + 1 > n，会在 19 后走到 20，而正确顺序应先回退并进入 2。
  • 把连续回退写成 if 会漏退祖先层，例如 n = 200 时从 199 之后应回到 1，再进入 2。
  • 下探条件若写成严格小于，会在 n = 10 时漏掉 10；用 cur <= n / 10 还能避免乘法溢出。
  • 不要用 while (cur <= n) 控制总循环：遍历完 9 后 cur 可能回到 1，导致重复；固定输出 n 个数字最稳妥。

相似题目

题目 难度 考察点
208. 实现 Trie (前缀树) 中等 显式前缀树的构建与查询
1061. 按字典序排列最小的等效字符串 中等 并查集下选最小等价代表
60. 排列序列 困难 按阶乘分段定位第 k 个排列
440. 字典序的第K小数字 困难 十叉树上按子树规模跳跃
1163. 按字典序排在最后的子串 困难 双指针求字典序最大后缀