☆打卡算法☆LeetCode 46、全排列 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个不含重复数字的数组，返回所有可能的全排列。”

题目链接：

来源：力扣（LeetCode）

链接：46. 全排列 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：
输入： nums = [1,2,3]
输出： [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：
输入： nums = [0,1]
输出： [[0,1],[1,0]]

二、解题

1、思路分析

看到返回所有结果的字样就要想到是不是可以用回溯法。

回溯法：一种通过探索所有可能的候选解来找出所有的解的算法，如果候选解被确定不是一个解，或者至少不是最后一个解，回溯算法会通过在上一步进行一些变化抛弃该解，即回溯并且再次尝试。

这道题，可以排列每一种组合，很直接就可以想到穷举的算法，即从左到右每个元素都取出进行组合。

2、代码实现

代码参考：

public class Solution {
    IList<IList<int>> list = new List<IList<int>>();
    public IList<IList<int>> Permute(int[] nums) {
        IList<int> l = new List<int>();
        Test(l, nums);
        return list;
    }

    void Test(IList<int> l, int[] nums)
    {
        if (nums.Length == l.Count)
        {
            //l.ToArray() 实现深拷贝 防止指针指向原来的对象 l 对象执行 RemoveAt 方法造成影响
            list.Add(l.ToArray());
            return;
        }

        for (int i = 0; i < nums.Length; i++)
        {
          if (l.Contains(nums[i]))
              continue;
            l.Add(nums[i]);
            Test(l, nums);
            l.RemoveAt(l.Count - 1);
        }
    }
}

3、时间复杂度

时间复杂度 ： O(n x n!)

其中n为序列的长度。

空间复杂度： O(n)

其中n为序列的长度。

三、总结

这类题目都是同一类型的,用回溯算法!

其实回溯算法关键在于:不合适就退回上一步

然后通过约束条件, 减少时间复杂度。