广州网站设计公司兴田德润在哪儿,注册公司取什么名字最佳,商务网站开发的基本流程,商城网站是免费开吗题目描述
全排列
给定一个不含重复数字的数组 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]]示例 2#xff1a;
输入…题目描述
全排列
给定一个不含重复数字的数组 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 中的所有整数 互不相同
解法
回溯法
这个问题可以看作有 n 个排列成一行的空格我们需要从左往右依此填入题目给定的 n 个数每个数只能使用一次。那么很直接的可以想到一种穷举的算法即从左往右每一个位置都依此尝试填入一个数看能不能填完这 n 个空格在程序中我们可以用「回溯法」来模拟这个过程。
定义回溯函数
private void backtrack(int n, ListInteger output, ArrayListListInteger res, int first) {
}first为当前要填的位置n位需要填的总位置数。
如果 firstn说明已经填完了 n 个位置注意下标从 0 开始找到了一个可行的解将 output 放入答案数组中递归结束。如果first n填第 first 个数的时候遍历题目给定的 n 个数如果这个数没有被标记过就尝试填入并将其标记继续尝试填下一个位置。假设我们已经填到第 first 个位置那么 nums 数组中 [0,first−1]是已填过的数的集合[first,n−1] 是待填的数的集合。
java代码
class Solution {/*** 回溯** param nums* return*/public ListListInteger permute(int[] nums) {ArrayListListInteger res new ArrayList();// nums不好交换位置使用ListListInteger output new ArrayListInteger();for (int num : nums) {output.add(num);}int n nums.length;// 使用回溯backtrack(n, output, res, 0);return res;}/*** 回溯算法* 如果 firstn说明已经填完了 n 个位置注意下标从 0 开始找到了一个可行的解将 output 放入答案数组中递归结束。* 如果first n填第 first 个数的时候遍历题目给定的 n 个数如果这个数没有被标记过就尝试填入并将其标记继续尝试填下一个位置* 假设我们已经填到第 first 个位置那么 nums 数组中 [0,first−1]是已填过的数的集合[first,n−1] 是待填的数的集合*** param n 原数组长度也是结果数组最后的总长度* param output 当前的数组* param res 结果数组* param first 当前位置*/private void backtrack(int n, ListInteger output, ArrayListListInteger res, int first) {// 已经填完了 n 个位置将 output 放入答案数组中递归结束if (first n) {// 注意这里的output每次递归是公用的所以需要把它放入新列表再放到结果列表res.add(new ArrayList(output));}// 开始填第first个数for (int i first; i n; i) {// 动态维护数组交换位置Collections.swap(output, first, i);// 继续递归填下一个数backtrack(n, output, res, first 1);// 回退需要吧位置交换回来Collections.swap(output, first, i);}}
}复杂度
时间复杂度O(n*n!)其中 n 为数组的长度空间复杂度O(n)。
