题解 | #没有重复项数字的全排列#

没有重复项数字的全排列

http://www.nowcoder.com/practice/4bcf3081067a4d028f95acee3ddcd2b1

/**
 * 解法一:回溯 + 递归
 * 思路:
 *   全排列就是对数组元素交换位置,使每--种排列都可能出现。因为题目要求按照字典序排
 *   列输出,那毫无疑问第-一个排列就是数组的升序排列,它的字典序最小,后续每个元素与
 *   它后面的元素交换一次位置就是一种排列情况,但是如果要保持原来的位置不变,那就不
 *   应该从它后面的元素开始交换而是从自己开始交换才能保证原来的位置不变,不会漏情况。
 * 时间复杂度: O(n!), n个元素的数组进行全排列
 * 空间复杂度: O(n), 递归栈的最大深度为数组长度n,res属于返回必要空间
 */
export function permute(num: number[]): number[][] {
    const res: number[][] = []
    if (num.length === 0) return res

    num.sort((a, b) => a - b)

    recursion(res, num, 0)

    return res
};

function recursion(res: number[][], nums: number[], index: number) {
    if (index === nums.length - 1) { // 分支进入结尾,找到一种排列
        res.push([...nums])
    } else {
        for (let i = index; i < nums.length; i++) {
            swap(nums, i, index) // 交换二者
            recursion(res, nums, index + 1) // 继续往后找
            swap(nums, i, index) // 回溯
        }
    }
}

function swap(nums: number[], index1: number, index2: number) {
    const temp = nums[index1]
    nums[index1] = nums[index2]
    nums[index2] = temp
}

一站式解决前端面试高频算法题

https://github.com/hovinghuang/fe-agorithm-interview

全部评论

相关推荐

只有一个苍穹外卖外加正在看黑马点评,可以找小厂实习吗,还有我的简历有什么大问题吗
Java抽象小篮子:感觉有点熟悉,问题1是学历,2是没实习经历,3是专业技能写得太少太少了(怎么写可以看我置顶帖),4是仅这一个项目找实习不够看。拷打完毕,简历怎么写可以看我置顶帖子
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务