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