文章目录
- 摘要
- 描述
- 题解答案
- 题解代码分析
- 示例测试及结果
- 时间复杂度
- 空间复杂度
- 总结
摘要
今天我们来聊聊一个有趣的数字排序问题——字典序排数。这个问题要求我们将从 1 到 n 的所有整数按照字典序排列。听起来可能有点抽象，但其实字典序排序在我们日常生活中随处可见。比如文件管理器里的文件排序，当我们看到 “10.txt” 排在 “2.txt” 之前时，这就是字典序排序的结果。这篇文章会详细解析 LeetCode 386 题的 Swift 解法，带你深入理解字典序排序的原理和实现方法。
描述
想象一下，你有一堆编号从 1 到 n 的文件，这些文件按照数字顺序排列时是 1, 2, 3, …, 10, 11, …。但如果你想让它们在文件管理器里按照"字典顺序"排列，那顺序就会变成 1, 10, 11, 12, …, 2, 20, 21, …。这就是字典序排序的效果——它把数字当作字符串来处理，按照字符串的比较规则来排序。
这个问题的难点在于，我们需要设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。这意味着我们不能简单地生成所有数字然后排序，因为排序通常需要 O(n log n) 的时间复杂度。我们需要找到一种更聪明的方法来按字典序生成这些数字。
在实际开发中，这种排序方式在文件系统、数据库索引、搜索引擎的搜索结果排序等场景中都有应用。理解这种排序方式不仅能帮助我们解决算法问题，还能在实际工作中处理类似需求时更有思路。
题解答案
对于字典序排序问题，最优雅的解法是使用深度优先搜索（DFS）的思想，或者更准确地说，使用"字典树遍历"的思路。我们可以把从 1 到 n 的所有数字想象成一颗十叉树，每个节点可以有 0 到 9 十个子节点，分别对应在该数字后面追加 0-9 这十个数字。
但是直接构建这样一颗树会占用太多空间，不符合 O(1) 额外空间的要求。所以我们采用模拟遍历的方式，从一个数字开始，尝试在这个数字后面追加 0-9，如果得到的新数字不超过 n，就继续深入；否则就回溯到上一层，尝试下一个数字。
具体来说，我们可以把每个数字看作一个字符串，然后按照如下规则生成下一个数字：
- 如果当前数字乘以 10 不超过 n，那么下一个数字就是当前数字乘以 10（相当于在末尾加 0）
- 否则，如果当前数字加 1 不超过 n 并且当前数字的个位数不是 9，那么下一个数字就是当前数字加 1
- 如果都不满足，就需要回溯：将当前数字除以 10（去掉最后一位），然后加 1，直到找到一个合适的数字
这种方法有点像我们在手机上输入数字时的感觉——先输入高位数字，然后逐渐输入低位数字，输完所有可能后再回到上一级尝试下一个数字。
题解代码分析
classSolution{funclexicalOrder(_n:Int)->[Int]{// 结果数组，预先分配容量以提高性能varresult=[Int]()result.reserveCapacity(n)// 从 1 开始varcurrent=1// 总共需要生成 n 个数字for_in0..<n{// 将当前数字加入结果result.append(current)// 尝试在当前数字后面加 0// 这相当于进入下一层深度ifcurrent*10<=n{current*=10}else{// 如果不能在后面加 0，就需要考虑其他情况// 如果当前数字已经达到 n 或者个位数是 9// 就需要回溯到上一级whilecurrent>=n||current%10==9{// 去掉最后一位，回到上一级current/=10}// 在当前层级尝试下一个数字current+=1}}returnresult}}让我详细解释一下这段代码的执行逻辑。我们用一个变量current来表示当前正在处理的数字。整个过程就像是在遍历一颗隐式的数字树：
首先，我们从数字 1 开始，这是字典序的第一个数字。然后我们尝试深入：如果current * 10不超过 n，我们就进入下一层，这相当于在数字末尾添加一个 0。比如从 1 变成 10，从 10 变成 100，依此类推。
当我们无法继续深入时（比如 13 * 10 = 130 已经超过了 n=13），我们就需要检查当前数字。如果当前数字已经等于 n，或者当前数字的个位数是 9（比如 19、29 等），这意味着在当前层级我们已经尝试完了所有可能的数字，需要回溯到上一层。
回溯的过程是通过current /= 10实现的，这相当于去掉数字的最后一位，回到父节点。比如从 13 回溯到 1，从 19 回溯到 1。
一旦我们回溯到合适的层级，我们就将当前数字加 1，继续遍历。比如从 13 回溯到 1 后，current变成 1，然后current += 1变成 2，这样我们就开始处理以 2 开头的数字序列了。
这个过程会一直持续，直到我们生成了 n 个数字为止。由于每个数字只被生成一次，且每个数字的处理时间是常数，所以总时间复杂度是 O(n)。我们只使用了几个变量来保存状态，所以额外空间复杂度是 O(1)。
让我们用一个具体的例子来理解这个过程。假设 n = 13，执行过程如下：
- 从 1 开始，加入结果：[1]
- 1 * 10 = 10 ≤ 13，current = 10，加入结果：[1, 10]
- 10 * 10 = 100 > 13，不能深入
- 检查 10：10 < 13 且个位不是 9，所以 10 + 1 = 11，加入结果：[1, 10, 11]
- 11 * 10 = 110 > 13，不能深入
- 检查 11：11 < 13 且个位不是 9，所以 11 + 1 = 12，加入结果：[1, 10, 11, 12]
- 12 * 10 = 120 > 13，不能深入
- 检查 12：12 < 13 且个位不是 9，所以 12 + 1 = 13，加入结果：[1, 10, 11, 12, 13]
- 13 * 10 = 130 > 13，不能深入
- 检查 13：13 = n，需要回溯。13 / 10 = 1
- 检查 1：个位是 9 吗？不是，所以 1 + 1 = 2，加入结果：[1, 10, 11, 12, 13, 2]
- 继续这个过程直到生成 13 个数字
这种方法的巧妙之处在于，它模拟了深度优先遍历的过程，但没有实际构建树结构，从而满足了空间复杂度的要求。
示例测试及结果
在 LeetCodeSwift 项目中，我们可以为这个解法添加专门的测试用例。测试代码应该独立于已有的代码，避免产生耦合。我们可以创建一个新的测试类或者扩展现有的测试类。
测试的关键是验证算法的正确性和性能。对于正确性，我们需要测试各种边界情况：
- n = 1 的最小情况
- n = 5 * 10^4 的最大情况
- 包含多位数字的情况
- 包含数字 9 的特殊情况（因为涉及到回溯逻辑）
对于性能，我们需要确保算法在最大输入规模下仍然能在合理时间内完成，并且不会占用过多内存。
在实际编写测试时，我们不仅要测试算法返回的结果是否正确，还可以测试一些中间状态，帮助我们理解算法的执行过程。不过要注意的是，测试代码应该专注于测试公共接口，而不是内部实现细节。
一个良好的测试套件应该能够给开发者信心，确保代码修改不会破坏现有功能。对于字典序排序这样的算法问题，全面的测试尤为重要，因为算法的逻辑相对复杂，容易在边界情况下出错。
时间复杂度
这个算法的时间复杂度是 O(n)，其中 n 是输入的数字上限。这个结论可能有些反直觉，因为看起来我们有一个循环嵌套另一个循环（回溯部分的 while 循环）。但仔细分析就会发现，每个数字最多被访问一次，每个数字的回溯操作的总次数也是有限的。
让我们详细分析一下：外层循环执行 n 次，每次处理一个数字。内层的 while 循环用于回溯，但回溯的总次数是有限的。实际上，每个数字最多被回溯一次，而回溯的深度（即 while 循环执行的次数）最多是数字的位数。在 n ≤ 50000 的情况下，数字最多有 5 位，所以回溯操作的总时间复杂度是 O(5n) = O(n)。
从另一个角度理解：整个算法相当于遍历了一颗隐式的十叉树，树中的每个节点恰好被访问一次。树中总共有 n 个节点，所以时间复杂度是 O(n)。
这种线性时间复杂度是非常优秀的，特别是考虑到我们需要生成一个有序序列。如果使用常规的排序算法，比如快速排序或归并排序，时间复杂度会是 O(n log n)。我们的算法通过利用字典序的特殊性质，达到了更好的时间复杂度。
空间复杂度
算法的空间复杂度是 O(1)，即常数额外空间。我们只使用了几个变量来保存当前状态：result数组用于存储结果（这是输出所需，不计入额外空间），current变量用于追踪当前位置，以及循环中的索引变量。
没有使用递归调用栈，没有使用额外的数据结构来存储中间结果。即使是回溯操作，也是通过简单的除法运算实现的，不需要栈结构。
这种常数空间复杂度对于内存受限的环境特别重要。在实际应用中，如果我们需要处理大量数据，但又不能占用太多内存，这种算法设计思路就很有价值。
需要注意的是，这里说的 O(1) 额外空间是指除了输出数组之外的空间。输出数组本身的大小是 O(n)，但这是问题要求的输出，不计入空间复杂度分析。
总结
字典序排数问题是一个很好的算法练习题，它结合了数学思维和算法设计技巧。通过这个问题，我们学习了如何在不实际构建数据结构的情况下模拟树的遍历，如何在有限的空间内实现复杂的逻辑。
这个问题的解法体现了算法设计中的一个重要原则：根据问题的特殊性设计专门的算法，而不是套用通用解法。通用排序算法需要 O(n log n) 时间，但通过利用字典序的特性，我们可以将时间复杂度降低到 O(n)。
在实际开发中，类似的思维模式也很有用。当我们遇到性能问题时，不要立即寻找更快的硬件或更优化的库，而是先思考：这个问题有没有特殊的性质？能不能设计一个更针对性的算法？
Swift 语言的特性也让这个算法的实现更加清晰和安全。Swift 的数组性能优秀，值语义避免了不必要的拷贝，类型安全减少了错误。虽然这个算法本身不依赖于 Swift 的特殊特性，但 Swift 的表达能力让算法的意图更加清晰。
希望通过这个问题的解析，你能不仅学会如何解决 LeetCode 386 题，更能理解算法设计的思想，并在实际工作中运用这些思想。记住，好的算法不仅仅是正确的，还应该是高效的、简洁的、易于理解的。
