一步步学懂 全排列 算法。
面试被问到全排列
记得之前刚开始学前端的时候还写过全排列,一晃三年过去了,之前怎么写的完全忘记了,说明还是当时没有完全理解全排列算法的精髓,这次好好整理一下。
先从最简单的含有重复数字的全排列写起来
题目里需要输出的结果为
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
我们可以先从可以重复的解法开始,具体来说,我们可以先输出这个结果
[
[1,1,1],
[1,1,2],
[1,1,3],
[1,2,1],
[1,2,2],
[1,2,3],
[1,3,1],
[1,3,2],
[1,3,3],
[2,1,1],
[2,1,2],
[2,1,3],
[2,2,1],
[2,2,2],
[2,2,3],
[2,3,1],
[2,3,2],
[2,3,3],
[3,1,1],
[3,1,2],
[3,1,3],
[3,2,1],
[3,2,2],
[3,2,3],
[3,3,1],
[3,3,2],
[3,3,3]
]
借助辅助图来看一下如何实现上面的结果
代码实现
function all(nums) {
const len = nums.length;
// 结果,是一个二维数组
const res = [];
// 中间结果
const curr = [];
function walk() {
// 递归首先确定终止条件,当前curr的长度等于nums的长度,表明此次已经收集够3个数了,终止此次递归
if (curr.length === len) {
res.push([...curr]);
return;
}
// 否则循环数组
for (let i = 0; i < len; i++) {
curr.push(nums[i]);
walk();
curr.pop();
}
}
walk();
return res;
}
进一步改造
function all(nums) {
const len = nums.length;
const res = [];
const curr = [];
// 记录当前数组是否出现过
const visited = {};
function walk() {
if (curr.length === len) {
res.push([...curr]);
return;
}
for (let i = 0; i < len; i++) {
// 如果出现过,继续下一轮循环
if (visited[nums[i]]) {
continue;
}
// 如果没有出现过,标记当前数字
curr.push(nums[i]);
visited[nums[i]] = true;
// 标记完后,继续下一次递归
walk();
// 上一次递归触发终止条件后,会返回到这里
// 在这里将当前数字从curr中弹出来,并移除标记
curr.pop();
visited[nums[i]] = false;
}
}
walk();
return res;
}