石家庄免费网站设计,最新版wordpress功能,公司创建的法制网站,六安网站自然排名优化价格全排列
https://leetcode.cn/problems/permutations/
描述
给定一个不含重复数字的数组 nums #xff0c;返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1
输入#xff1a;nums [1,2,3]
输出#xff1a;[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,…全排列
https://leetcode.cn/problems/permutations/
描述
给定一个不含重复数字的数组 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]]示例 3
输入nums [1]
输出[[1]]提示
1 nums.length 6-10 nums[i] 10nums 中的所有整数 互不相同
算法实现
1 回溯1: 基于数组
function permute(nums: number[]): number[][] {const res: number[][] [];// 回溯函数const backtrack (path: number[]) {// 满足当前条件if(path.length nums.length) {res.push(path);return;}// 遍历for(let i 0; i nums.length; i) {if(path.includes(nums[i])) continue;backtrack(path.concat(nums[i]));}}backtrack([]);return res;
}时间复杂度O(n*n!) 假设输入数组的长度为 n遍历每个元素的时间复杂度为 O(n)对于每个元素都会进行递归调假设数组中有 n 个不同的元素那么对于每个元素都会有 n-1 个可能的选择然后对于每个选择又会有 n-2 个可能的选择以此类推因此递归的时间复杂度可以表示为 O(n!)。在每一层递归中都会进行一次包含操作includes其时间复杂度为 O(n)。综合考虑这段代码的时间复杂度为 O(n * n!)其中 n 表示输入数组的长度。需要注意的是这里的时间复杂度分析基于平均情况。在最坏情况下全排列的数量是 n!因此在最坏情况下时间复杂度为 O(n * n!)注意: n的阶乘公式: n! 1*2*3*...*(n-1)*n 空间复杂度O(n) 递归堆栈不是常量是线性增长的是递归的层数
2 回溯2: 基于交换
function permute(nums: number[]): number[][] {const res: number[][] [];const backtrack function(start: number) {if (start nums.length - 1) {res.push([...nums]);return;}for (let i: number start; i nums.length; i) {[nums[i], nums[start]] [nums[start], nums[i]]; // 交换backtrack(start 1); // 下一个数[nums[i], nums[start]] [nums[start], nums[i]]; // 交换撤销}}backtrack(0); // 从 0 开始return res;
};这个问题可以看作有 n 个排列成一行的空格我们需要从左往右依此填入题目给定的 n 个数每个数只能使用一次那么很直接的可以想到一种穷举的算法即从左往右每一个位置都依此尝试填入一个数看能不能填完这 n 个空格在程序中我们可以用「回溯法」来模拟这个过程时间复杂度O(n*n!)其中 n 为序列的长度空间复杂度O(n)
回溯算法、递归和深度优先遍历DFS之间存在密切的关系 它们通常在算法中一起使用因为回溯算法通常使用递归来实现并且常常涉及到深度优先遍历的思想。 回溯算法与递归 回溯算法是一种渐进式寻找并构建问题解决方案的策略。在回溯算法中通常通过递归的方式来尝试所有可能的情况。当找到一个可能的解决方案时它会继续探索下去如果发现不符合条件就会回溯到上一个状态尝试其他可能的情况。因此回溯算法通常使用递归来实现因为递归天然地适合于处理这种尝试所有可能情况的问题。 回溯算法与深度优先遍历 回溯算法通常使用深度优先遍历的思想。在回溯算法中我们会尝试一条路走到底直到无法再继续下去然后回溯到上一个状态尝试其他的可能性。这与深度优先遍历的思想是一致的深度优先遍历也是尽可能深地搜索树的分支直到无法再继续为止然后回溯到上一个节点继续搜索其他分支 因此回溯算法通常使用递归来实现并且其思想与深度优先遍历密切相关。 在许多情况下回溯算法可以被视为一种特殊的深度优先遍历。
