作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
题目描述
给定一个不含重复数字的数组 nums，返回其所有可能的全排列。你可以以任意顺序返回答案。
输入格式
- nums：一个整数数组。
输出格式
- 返回一个列表，包含所有可能的排列。
示例
示例 1
输入: nums = [1,2,3] 输出: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
示例 2
输入: nums = [0,1] 输出: [[0,1], [1,0]]
方法一：回溯算法
解题步骤
- 初始化：创建一个空列表
res来存储所有排列结果。 - 递归函数：编写一个递归函数，使用当前序列
path和选择列表nums来生成排列。 - 结束条件：如果
path的长度等于nums的长度，则将path添加到结果列表res中。 - 循环选择：遍历
nums中的每个数字，如果数字未被选择，则加入到path，并继续递归，最后撤销选择。
完整代码
def permute(nums): """ 使用回溯算法生成数组的全排列 :param nums: List[int], 输入的整数数组 :return: List[List[int]], 所有可能的全排列 """ def backtrack(path, options): # 如果当前路径的长度等于输入数组的长度，说明找到了一种排列 if len(path) == len(nums): res.append(path[:]) return # 遍历当前可选择的数字 for i in range(len(options)): # 选择当前数字 path.append(options[i]) # 继续递归填下一个数 backtrack(path, options[:i] + options[i+1:]) # 撤销选择 path.pop() res = [] backtrack([], nums) return res # 示例调用 print(permute([1, 2, 3])) # 输出: [[1, 2, 3], [1, 3, 2], ..., [3, 2, 1]]
算法分析
- 时间复杂度：(O(n! \times n))，生成所有排列需要 (n!) 次调用，每次调用处理列表需要 (O(n)) 时间。
- 空间复杂度：(O(n))，递归深度为 (n)，使用了额外的空间存储当前排列。
方法二：字典序生成算法
解题步骤
- 排序：先将数组排序。
- 查找：从右向左查找第一个升序的相邻元素对
(i, j)，即nums[i] < nums[j]。 - 交换与反转：如果找到，再从右向左查找第一个大于
nums[i]的元素nums[k]，交换nums[i]和nums[k]，然后反转i+1到末尾的元素。 - 重复：重复以上步骤直到完全逆序。
完整代码
def permute(nums): """ 使用字典序算法生成数组的全排列 :param nums: List[int], 输入的整数数组 :return: List[List[int]], 所有可能的全排列 """ def next_permutation(perm): # 找到升序的边界 i = len(perm) - 2 while i >= 0 and perm[i] >= perm[i + 1]: i -= 1 if i == -1: return False # 找到需要交换的位置 j = len(perm) - 1 while perm[j] <= perm[i]: j -= 1 perm[i], perm[j] = perm[j], perm[i] # 反转i后面的部分 perm[i + 1:] = perm[i + 1:][::-1] return True nums.sort() res = [nums[:]] while next_permutation(nums): res.append(nums[:]) return res # 示例调用 print(permute([1, 2, 3])) # 输出: [[1, 2, 3], [1, 3, 2], ..., [3, 2, 1]]
算法分析
- 时间复杂度：(O(n! ✖️ n))，尽管每次生成下一个排列只需要 (O(n)) 时间，但总共有 (n!) 个排列。
- 空间复杂度：(O(1))，除了输出数组外，空间使用是常数。
方法三：递归交换
解题步骤
- 递归函数定义：定义一个递归函数，使用当前索引
start来处理排列。 - 递归终止条件：如果
start等于数组长度，记录当前排列。 - 递归交换：从
start开始，将每个元素交换到start位置，然后递归处理start + 1。
完整代码
def permute(nums): """ 使用递归交换方法生成数组的全排列 :param nums: List[int], 输入的整数数组 :return: List[List[int]], 所有可能的全排列 """ def backtrack(start): if start == len(nums): res.append(nums[:]) return for i in range(start, len(nums)): nums[start], nums[i] = nums[i], nums[start] backtrack(start + 1) nums[start], nums[i] = nums[i], nums[start] res = [] backtrack(0) return res # 示例调用 print(permute([1, 2, 3])) # 输出: [[1, 2, 3], [1, 3, 2], ..., [3, 2, 1]]
算法分析
- 时间复杂度：(O(n! ✖️ n))，需要进行 (n!) 次调用，每次调用中进行的操作与 (n) 成正比。
- 空间复杂度：(O(n))，递归深度最大为 (n)，使用了额外的空间存储当前排列状态。
总结
为了直观地比较解决LeetCode题目46 "全排列"的三种方法，下面的表格将展示它们在不同技术维度的性能和特点，包括时间复杂度、空间复杂度以及各自的优势和劣势。
| 特征 | 方法一：回溯算法 | 方法二：字典序算法 | 方法三：递归交换法 |
| 时间复杂度 | (O(n! \times n)) | (O(n! \times n)) | (O(n! \times n)) |
| 空间复杂度 | (O(n)) | (O(1)) | (O(n)) |
| 优势 | - 灵活且直观 - 易于实现和理解 |
- 非递归，避免栈溢出 - 效率高于普通回溯 |
- 实现简单 - 直接在输入数组上操作 |
| 劣势 | - 空间消耗较大 - 深度递归可能导致栈溢出 |
- 实现复杂度较高 - 不如回溯直观 |
- 多次交换操作复杂 - 递归依旧可能栈溢出 |
| 适用场景 | - 需要所有可能解时 - 教学和基础算法学习 |
- 需要按字典顺序生成全排列 - 大规模数据处理 |
- 内存使用敏感 - 喜欢简洁代码风格 |
综合分析
方法一（回溯算法）：
- 回溯算法是解决排列、组合问题的经典方法，非常直观，可以灵活地处理各种约束条件。其主要缺点是在深度递归时可能会消耗较多内存，特别是在解空间非常大时。
方法二（字典序算法）：
- 字典序算法提供了一种非递归的解决方案，能够有效地按照字典顺序生成下一个排列，适用于需要顺序输出或者大数据量的问题。然而，这种方法在实现上较为复杂，可能不太直观。
方法三（递归交换法）：
- 递归交换法通过直接在输入数组上进行操作，避免了额外的空间使用，简化了代码的复杂性。但与回溯类似，它的缺点是递归深度大时仍可能导致栈溢出问题，且多次交换操作可能相对复杂。
在选择合适的方法时，可以根据具体问题的需求、可用资源以及开发时间来做决策。例如，对于教学或基础学习，推荐使用回溯算法；对于工业级应用，考虑字典序算法；而对于内存敏感或喜欢简洁代码的场景，递归交换法可能是一个好选择。
欢迎关注微信公众号 数据分析螺丝钉
