做公司网站棋牌,济南产品网站建设外包,做网站应该先从什么地方开始,东莞做网站注意事项优质博文#xff1a;IT-BLOG-CN
一、题目
给定一个不含重复数字的数组nums#xff0c;返回其所有可能的全排列。你可以按任意顺序返回答案。
示例 1#xff1a; 输入#xff1a;nums [1,2,3] 输出#xff1a;[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例…优质博文IT-BLOG-CN
一、题目
给定一个不含重复数字的数组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] 10 nums 中的所有整数 互不相同 二、代码
全排列的长度就是数据长度的阶层排列和组合的区别排列中[1,2]和[2,1]是不同的但在组合中[1,2]和[2,1]是相同的。
我们已简单的[1,2,3]为一组看下排列的搜索树 解题思路 【1】使用数组path记录路径上的数已选数字 【2】集合s记录剩余未选的数
回溯三问 【1】当前操作从s中枚举path[i]要填入的数字x 【2】子问题构造排列 i 的部分剩余未选数字集合为s 【3】下一个子问题构造排列 i 1 部分剩余未选数字结合为s-{x}
class Solution {// 入参private int[] nums;// 返回值private final ListListInteger resList new ArrayList();// 返回值中包的Listprivate ListInteger path;// 过滤 j 使用private boolean[] onPath;public ListListInteger permute(int[] nums) {this.nums nums;path Arrays.asList(new Integer[nums.length]);onPath new boolean[nums.length];dfs(0);return resList;}// 回溯方法private void dfs(int i) {// 回溯方法的退出条件if (i nums.length) {// 这里需要copy path, 不能直接赋值因为path一直变化resList.add(new ArrayList(path));System.out.println(resList : resList.toString());return;}// 每个i进来组装一次结果for (int j 0; j nums.length; j) {// 过滤j原因在循环中有说明if (!onPath[j]) {// 当 i 递增时j也在递增path.set(i, nums[j]);System.out.println(path.toString());// 回溯 (此时i 1调用的时候j还是0所以需要过滤掉j0因此添加 onPath 的Boolean数组)onPath[j] true;dfs(i1);// 当i遍历完成之后需要恢复现场onPath[j] false;}}}
}看下输出的流程
[1, null, null]
[1, 2, null]
[1, 2, 3]
resList : [[1, 2, 3]]
[1, 3, 3]
[1, 3, 2]
resList : [[1, 2, 3], [1, 3, 2]]
[2, 3, 2]
[2, 1, 2]
[2, 1, 3]
resList : [[1, 2, 3], [1, 3, 2], [2, 1, 3]]
[2, 3, 3]
[2, 3, 1]
resList : [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]]
[3, 3, 1]
[3, 1, 1]
[3, 1, 2]
resList : [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]]
[3, 2, 2]
[3, 2, 1]
resList : [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]附视频讲解
时间复杂度 O(n⋅n!)其中n为nums的长度。搜索树中的节点个数低于3⋅n!。实际上精确值为⌊e⋅n!⌋其中e2.718⋯为自然常数。每个非叶节点要花费O(n)的时间遍历onPath数组每个叶结点也要花费O(n)的时间复制path数组因此时间复杂度为O(n⋅n!)。 空间复杂度 O(n)返回值的空间不计入。
