LeetCode-46-全排列

回溯算法

原题地址：全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [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