LeetCode 386 字典序排数 Swift 题解：模拟字典翻页的遍历技巧 - 实践

文章目录

• • 摘要
  • 描述
  • 题解答案
  • 题解代码分析
  • • 代码拆解
  • 示例测试及结果
  • 时间复杂度
  • 空间复杂度
  • 总结

摘要

在日常开发中，我们有时会需要把一批数字 按字典序 排列，而不是常规的数值大小排序。比如文件名 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)。

总结

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

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

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