Permutations(Medium)排列
Given a collection of distinct numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
解题思路1:回溯+DFS
解题思路: 看到这道题,首先第一想法应该是用递归来求解.如果要是用循环来求解,这个时间复杂度应该是比较恐怖了.并且,这个递归是一层一层往深处去走的,打个比方,我们一个循环,首先求得以1开始的看个数的combination,之后再求以2开始的,以此类推,所以开始是对n个数做DFS, n-1个数做DFS...所以应该是对n(n-1)...*1做DFS. 在程序中,我们可以加一些剪枝条件来减少程序时间.
时间复杂度: 在题目分析中,我们提到了对于对n,n-1,...,1做DFS,所以时间复杂度是O(n!)
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (nums == null || nums.length == 0) return result;
List<Integer> list = new ArrayList<Integer>();
dfs(nums, list, result);
return result;
}
private void dfs(int[] nums, List<Integer> current, List<List<Integer>> result) {
if (current.size() == nums.length) {
result.add(new ArrayList<Integer>(current));
return;
}
for (int i = 0; i < nums.length; i++) {
if (current.contains(nums[i]))
continue;
current.add(nums[i]);
dfs(nums, current, result);
current.remove(current.size() - 1);
}
}
解题思路2: 迭代,使用Next Permutaion的思想
复杂度
时间 O(N^2) 空间 O(N) 递归栈
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (nums == null || nums.length == 0) return result;
Arrays.sort(nums);
while (true) {
// step0: add nums into result
List<Integer> list = new ArrayList<Integer>();
for (int i : nums) {
list.add(i);
}
result.add(list);
// step2: find the first nums[k] < nums[k + 1] from the end to start
int k = -1;
for (int i = nums.length - 2; i >= 0; i--) {
if (nums[i] < nums[i + 1]) {
k = i;
break;
}
}
if (k == -1) break;
// step3: find the first nums[l] > nums[k] from the end to start
int l = nums.length - 1;
while (nums[l] <= nums[k]) {
l--;
}
// step3: swap between l and k
int temp = nums[l];
nums[l] = nums[k];
nums[k] = temp;
// step4: reverse between k + 1, nums.length - 1
reverse(nums, k + 1, nums.length - 1);
}
return result;
}
private void reverse(int[] nums, int lb, int ub) {
while (lb < ub) {
int temp = nums[lb];
nums[lb] = nums[ub];
nums[ub] = temp;
lb++;
ub--;
}
}