原题地址:全排列
给定一个没有重复数字的序列,返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
逐字插入
将每个数字插入前面数字的每个排列的每个可插入位置即可:
/**
* @param {number[]} nums
* @return {number[][]}
*/
const permute1 = function(nums) {
let result = [[nums[0]]]; // 一个数字的排列只有一种
for (let i = 1; i < nums.length; i ++) {
let array = [];
for (let j = 0; j < result.length; j ++) {
for (let k = 0; k <= i; k ++) {
// 对前面数字的每一种排列,将当前数字插入到这些排列中的每一个位置
let temp = [...result[j]];
temp.splice(k,0,nums[i]);
array.push(temp);
}
}
result = array;
}
return result;
};
测试:
let start = new Date();
const test = permute1;
/**
[
[ 3, 2, 1 ],
[ 2, 3, 1 ],
[ 2, 1, 3 ],
[ 3, 1, 2 ],
[ 1, 3, 2 ],
[ 1, 2, 3 ]
]
*/
console.log(test([1,2,3]));
console.log(new Date().getTime() - start.getTime()); // 9
时间复杂度: 时间复杂度为$O(N!)$,N为序列为数字的数目
空间复杂度: 空间复杂度也是$O(N!)$
本文由 李海平 创作,采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
最后编辑时间为: Aug 13,2019