全排列
描述
示例 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]]
提示
算法实现
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)
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)
回溯算法、递归和深度优先遍历之间的关系
-
回溯算法与递归
原文地址:https://blog.csdn.net/Tyro_java/article/details/134689827
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_45052.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。