九章算法 | 微软面试题:全排列
程序员文章站
2022-07-14 17:23:42
...
给定一个数字列表,返回其所有可能的排列。
在线评测地址:LintCode 领扣
样例 1:
输入:[1]
输出:
[
[1]
]
样例 2:
输入:[1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
算法:DFS(回溯法)
算法分析
对于全排列,比如[1,2,3]的全排列,我们按顺序穷举,步骤如下: 1. 首先会固定第一位为 1,然后第二位如果取2,最后一位只能是3;再可以把第二位变成3,第三位就只能是2; 2. 接下来变化第一位变成 2,然后再像上述的过程穷举后两位分别是1,3; 3. 最后第一位是3,再穷举后两位分别是1,2,整个过程就完成了。
以上的过程,很适合使用DFS(回溯法)进行实现。
算法步骤
- 根据题目要求,首先需要定义并初始化一个布尔类型used数组记录每个数字是否已被使用,一个数组current记录当前遍历的排列,一个二维数组results记录所有结果;
- 对输入的数字列表nums进行深度优先搜索,传入的参数包括:数字列表nums、used、current、results;
- 边界条件:当current中的元素个数和nums的相同,代表一次遍历完毕,将当前的current加入results并return;
- 遍历nums,如果nums中当前这个元素未被使用,则在used中标记其已使用,将其加入current,并递归调用dfs;
- 调用完毕后需要回退,即在used中标记其未使用;
复杂度分析
- 时间复杂度:
- 对于每一位,可以从n个元素中选择k个来放置,共有n位。
- 空间复杂度:O(N!)
- 共有N!个全排列,故需要保存N!个解
import java.util.ArrayList;import java.util.List;
public class Solution {
/*
* @param nums: A list of integers.
*
* @return: A list of permutations.
*/
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
// 如果数组为空直接返回空
if (nums == null) {
return results;
}
//dfs
dfs(nums, new boolean[nums.length], new ArrayList<Integer>(), results);
return results;
}
private void dfs(int[] nums, boolean[] used, List<Integer> current, List<List<Integer>> results) {
//找到一组排列,已到达边界条件
if (nums.length == current.size()) {
results.add(new ArrayList<Integer>(current));
return;
}
for (int i = 0; i < nums.length; i++) {
//i位置这个元素已经被用过
if (used[i]) {
continue;
}
//继续递归
current.add(nums[i]);
used[i] = true;
dfs(nums, used, current, results);
used[i] = false;
current.remove(current.size() - 1);
}
}
}
更多题解参考:九章算法