摘要

在日常开发中，我们有时会需要把一批数字 按字典序 排列，而不是常规的数值大小排序。比如文件名 file1, file2, file10, file11，按照数值大小排应该是 1,2,10,11，但如果是字典序就会变成 1,10,11,2。

这道题要求我们从 1 到 n 的所有整数，按字典序输出，而且时间复杂度必须是 O(n)，空间 O(1)。看起来像是一个遍历问题，但其实有点像在 翻字典页。

描述

题目给定一个整数 n，要求输出 [1...n] 之间的所有整数，按字典序排列。

比如：

• 输入 n = 13，输出应该是 [1,10,11,12,13,2,3,4,5,6,7,8,9]。
• 输入 n = 2，输出 [1,2]。

而且我们要在 O(n) 时间 + O(1) 空间 内完成，不能靠排序来做。

题解答案

最直观的想法可能是：

1. 先生成 [1...n] 的数组。
2. 转成字符串排序。

但是这样会需要 O(n log n) 时间，明显不符合要求。

题目的正确解法是 模拟字典树（Trie）的遍历顺序。

• 从 1 开始，把它当作前缀。
• 每次尝试进入更深层（比如从 1 到 10）。
• 如果无法深入，就回退到上一个兄弟（从 19 回退到 2）。

这种方法其实就是在用数字直接模拟字典序，而不是把它们真的转成字符串。

题解代码分析

Swift 代码如下：

import Foundation

class Solution {
    func lexicalOrder(_ n: Int) -> [Int] {
        var result: [Int] = []
        var current = 1
        
        for _ in 1...n {
            result.append(current)
            
            if current * 10 <= n {
                // 优先进入更深层，比如 1 -> 10
                current *= 10
            } else if current % 10 != 9 && current + 1 <= n {
                // 如果还能往右走，比如 1 -> 2
                current += 1
            } else {
                // 回退到上一个父节点，比如 19 -> 2
                while current % 10 == 9 || current + 1 > n {
                    current /= 10
                }
                current += 1
            }
        }
        
        return result
    }
}

代码拆解

1. 起点：从 1 开始。
2. 优先进入子节点：如果 current * 10 <= n，说明还能下钻，比如从 1 -> 10。
3. 进入兄弟节点：如果 current + 1 <= n，就往右，比如 1 -> 2。
4. 回退：如果到头了（比如 19），就往上回退，再加一。

这种方法就像在用数字模拟 DFS 遍历字典树。

示例测试及结果

我们写一个 Demo 来验证：

let solution = Solution()

let ex1 = 13
print("输入: \(ex1)")
print("输出: \(solution.lexicalOrder(ex1))\n")

let ex2 = 2
print("输入: \(ex2)")
print("输出: \(solution.lexicalOrder(ex2))\n")

运行结果：

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

输入: 2
输出: [1, 2]

完全符合题目要求。

时间复杂度

• 我们只遍历了 1...n 的所有数字，每个数字都处理一次，所以是 O(n)。
• 没有额外的排序开销，效率很高。

空间复杂度

• 结果数组本身需要 O(n)。
• 算法逻辑部分只用一个变量 current，所以额外空间是 O(1)。

总结

这道题的精髓在于 不用排序，而是直接按字典序遍历数字。

• 它模拟的是一个“字典树遍历”的过程：优先下钻、其次右移、最后回退。
• 这种技巧在实际中也很常见，比如分页系统里的编号排序、日志文件排序、甚至数据库里的字符串索引扫描。

对开发者来说，这个题的意义在于学会从 字典序的生成过程 来思考，而不是事后再去排序。