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

推荐阅读

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

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

一、题目

1、算法题目

“给定一个可以包含重复数字的序列，按任意顺序返回所有不重复的全排列”

题目链接：

来源：力扣（LeetCode）

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

2、题目描述

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

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

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

二、解题

1、思路分析

这个题是上一题全排列的进阶，序列中包含了重复的数字，要求返回不重复的全排序，当然还可以使用回溯法来解题。

2、代码实现

代码参考：

public class Solution {
    public IList<IList<int>> PermuteUnique(int[] nums) {
        //DFS
        Queue<List<int>> container = new Queue<List<int>>();
        Queue<List<int>> usedIndex = new Queue<List<int>>();

        container.Enqueue(new List<int>());
        usedIndex.Enqueue(new List<int>());
        Array.Sort(nums);

        //一共需要执行的层数
        for(int layer=0;layer<nums.Length;layer++){
            //记录容器当前层的数据个数
            int cnt = container.Count;
            for(int i=0;i<cnt;i++){
                var data = container.Dequeue();
                var used = usedIndex.Dequeue();
                int lastUse = -11;
                for(int j=0;j<nums.Length;j++){
                    //查找当前数字是否使用过
                    if(!used.Contains(j) && lastUse!=nums[j]){
                        //如果没有就复制前面层的所有数字并加入这个特殊数字
                        var temp = new List<int>(data);
                        var tempIndex = new List<int>(used);
                        temp.Add(nums[j]);
                        tempIndex.Add(j);
                        lastUse = nums[j];
                        container.Enqueue(temp);
                        usedIndex.Enqueue(tempIndex);
                    }
                }
            }
        }
        List<IList<int>> res = new List<IList<int>>(container);
        return res;
    }
}

3、时间复杂度

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

其中n为序列的长度。

空间复杂度： O(n)

只需要O(n)的标记数组。

三、总结

当然还有一种更简单的思路：

正常维护一个哈希表，然后再维护一个局部变量prev，用于保存在本地递归中循环选择里上一次访问的元素值。

每次选择与上一次访问值不同即可。

因为重复的本质是，多次选择了值相同的元素。

相同的值对于排序来说是一样的。