LeetCode 47. Permutations II

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 47. Permutations II 原题链接中等

作者：

yxc , 2018-04-21 14:14:50 , 所有人可见 , 阅读 7957

31

26

题目描述

给定一堆整数，可能包含相同数，返回其所有不同的全排列。

样例

输入：

[1,1,2]

输出：

[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

算法

(回溯) $O(n!)$

由于有重复元素的存在，这道题的枚举顺序和 Permutations 不同。

先将所有数从小到大排序，这样相同的数会排在一起；
从左到右依次枚举每个数，每次将它放在一个空位上；
对于相同数，我们人为定序，就可以避免重复计算：我们在dfs时记录一个额外的状态，记录上一个相同数存放的位置 $start$ ，我们在枚举当前数时，只枚举 $start+1, start+2, …, n$ 这些位置。
不要忘记递归前和回溯时，对状态进行更新。

时间复杂度分析：搜索树中最后一层共 $n!$ 个节点，前面所有层加一块的节点数量相比于最后一层节点数是无穷小量，可以忽略。且最后一层节点记录方案的计算量是 $O(n)$ ，所以总时间复杂度是 $O(n \times n!)$ 。

C++ 代码

class Solution {
public:
    vector<bool> st;
    vector<int> path;
    vector<vector<int>> ans;

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        st = vector<bool>(nums.size(), false);
        path = vector<int>(nums.size());
        dfs(nums, 0, 0);
        return ans;
    }

    void dfs(vector<int>& nums, int u, int start)
    {
        if (u == nums.size())
        {
            ans.push_back(path);
            return;
        }

        for (int i = start; i < nums.size(); i ++ )
            if (!st[i])
            {
                st[i] = true;
                path[i] = nums[u];
                if (u + 1 < nums.size() && nums[u + 1] != nums[u])
                    dfs(nums, u + 1, 0);
                else
                    dfs(nums, u + 1, i + 1);
                st[i] = false;
            }
    }
};

46 评论

ssssssssssssp-offer 2020-06-20 14:11

只用一个变量dfs可能更直观一些？

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<int> nums;
    vector<bool> vis;
    vector<vector<int>> permuteUnique(vector<int>& data) {
        nums=data;
        vis=vector<bool> (data.size(),false);
        sort(nums.begin(),nums.end());
        dfs(0);
        return res;
    }

    void dfs(int step)
    {
        if(step==nums.size())
        {
            res.push_back(path);
            return;
        }
        for(int i=0;i<vis.size();++i)
        {
            if(!vis[i])
            {
                if(i>0 && nums[i]==nums[i-1] && !vis[i-1])
                    continue;
                vis[i]=true;
                path.push_back(nums[i]);
                dfs(step+1);
                path.pop_back();
                vis[i]=false;
            }
        }
        return;
    }
};

yxc 2020-07-17 10:15

可以的，选择自己最习惯的方式即可。

Omega_ 2020-03-08 18:29

这代码咋想出来的这题要是第一次做能写出这样的代码真的太可怕了

yxc 2020-03-13 22:48

多练练就好了hh

Omega_ 2023-04-21 00:36 回复了 yxc 的评论

过了三年再看当初的自己哈哈好菜啊这么简单的问题都害怕 y总帮我提升了太多

一苇 2019-09-17 18:54

这个解法中，如果path没指定长度，用pushback放。 popback还原。结果就错了，因为是i位置放了nums[u]后u+1可能放在0，肯定不一定是i+1的位置，自己mark一下。数分别放在哪个位置上！

Team_ByuN 2019-09-19 11:02

感谢，正在纠结错在哪了🤔

yxc 2019-09-20 14:32

对滴，总结的不错

Parrie 2020-03-02 22:14

可以把nums看作物品栏，然后选择数字放入列中，如果path指定长度，则是放入具体的位置中，如果不指定长度，这是放入特定的列中，核心思路就是现在放入列中的数，如果之前存在相同的数，必须要被放在前面，这样才保证不重复。如果之前相同的数不在前面，说明已经被算过了，就只能剪枝，continue了

yxc 2020-03-03 10:47 回复了 Parrie 的评论

不错。

丐明 2020-03-30 14:13

看懂了，本质就是对于重复的点之间相对位置不变。如[1,1,1,3,3],在放第一个1的位置后，后面的1不能放在其前面，这样就避免了重复，但有一个影响代码性能的点是，如果第一个1放在了path[3]的位置，那么对于第三个1就没有位置可以放了，可能这么点冗余的遍历数组导致性能稍微下降吧。

yxc 2020-04-04 18:31

这里可以稍微优化一下，不过不影响时间复杂度。

cznczai 2019-08-20 13:54

class Solution {
    private int n;
    private List ls;
    private boolean[] bool;
    private LinkedList path;

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        n = nums.length;
        ls = new ArrayList<LinkedList>();
        path = new LinkedList<Integer>();
        bool = new boolean[n];
        dfs(nums, 0);
        return ls;
    }

    private void dfs(int[] nums, int u) {
        if (u == n) {
            ls.add(path.clone());
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!bool[i]) {
                if (i >= 1 && nums[i] == nums[i - 1] && bool[i - 1] == false)    // if bool[i-1] ==true 的话 选择i位置 即可以满足条件 1
                                                                                 // 2 1 i-1的位置比i快选择 
                                                                                //如果i-1 还没选 而 在选i的时候 就可以直接跳出 说明已经重复选择i位置了
                    // 第n趟递归是要在第n个位置选择一个数放置
                    // num[i-1]会比nums[i]早被考虑放到当前位置上
                    // 若bool[i-1]=false说明这个数在上一个排列中已经在这个位置放置过了
                    // 所以当前位置不应该再放置与nums[i-1]相等的nums[i] 
                    continue;
                path.add(nums[i]);
                bool[i] = true;
                dfs(nums, u + 1);
                bool[i] = false;
                path.removeLast();
            }
        }
    }
}

yxc 2019-08-20 13:57

很棒！

loosen 2020-01-27 18:20

很好理解，感谢！

周小伦 2020-02-26 22:24

大佬总结的真好

binzi98 2022-03-25 09:55

我的理解是类似数组排序中的稳定性，相等的数字也要保持相对的顺序，就不会出现重复的排列了。

亮亮 2020-02-26 07:04

//不需要提前排序，只需要遵循简单原则
//在进行dfs的时候
//1 同一层不许出现相同的数字（每层开个unordered_set来记录使用过的数字）
// 2 不同层不许使用同一位置的数字（开一个vector<bool>用来记录dfs时使用过哪些位置，并以引用传递，所有层共享）
class Solution {
    void dfs(vector<int>& nums,vector<bool>& usedPos,vector<vector<int>>& ret,int level,vector<int>& cur){
        int col = nums.size();
        if(level == col){
            ret.push_back(cur);
        }else{
            unordered_set<int> used;
            for(int i = 0; i < col; i++){
                if(used.find(nums[i]) == used.end() && !usedPos[i]){
                    used.insert(nums[i]);
                    usedPos[i] = true;
                    cur.push_back(nums[i]);
                    dfs(nums,usedPos,ret,level+1,cur);
                    cur.pop_back();
                    usedPos[i] = false;
                }  
            }
        }
    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> ret;
        int col = nums.size();
        if(col){
            vector<int> cur;
            vector<bool> usedPos(col,false);
            dfs(nums,usedPos,ret,0,cur);
        }
        return ret;
    }
};

yxc 2020-02-27 14:46

不错，这里很灵活，只要能避免重复即可。排序也是不影响最坏时间复杂度的，因为 $(nlogn)$ 相比于 $(n!)$ 是无穷小量。

一只菜鸡 2019-07-31 08:23

基于permutationI y总的代码改的，在枚举一个位置的情况时用一个单独变量记录这次用过的数，以后的枚举会跳过这个数，代码如下：

vector<vector<int>> ans;
    vector<int> path;
    vector<bool> in_use;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
       if (nums.size() == 0) return ans;
        for (int i =0;i < nums.size(); i++) in_use.push_back(false);
        sort(nums.begin(), nums.end());
        for (const auto & e : nums) cout<<e<<" ";
        dfs(nums, 0);
        return ans;
    }

    void dfs(vector<int>& nums, int  u)
    {
        if (u == nums.size()) {
            ans.push_back(path);
            return;
        }
        int prev = 0; 
        bool first = true;
        for (int i = 0; i < nums.size(); i++)
        {
            if (!in_use[i] && ( first || nums[i] != prev)) {
                in_use[i] = true;
                path.push_back(nums[i]);
                dfs(nums, u+1);
                in_use[i] = false;
                path.pop_back();
                prev = nums[i];
                if (first) first = false;
            }
        }
    }

yxc 2019-08-02 01:54

不错！这种搜索顺序也是可以的hh

比比多味豆 2019-07-20 12:27

用一个map记录每个数出现几次，枚举的时候遍历map，只要保证枚举每一个位置的时候可选择的数没有重复的就可以了，这样是不是空间复杂度比较大？

yxc 2019-07-21 19:44

这样怎么保证答案不会有重复呢？

比比多味豆 2019-07-21 23:34 回复了 yxc 的评论

class Solution {
public:
    map<int,int> mp;
    vector<vector<int>> res;
    int m;

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        m=nums.size();
        for(int i=0;i<nums.size();i++)
        {
            map<int,int>::iterator it=mp.find(nums[i]);
            if(it!=mp.end())
            {
                it->second+=1;
            }
            else
            {
                mp.insert({nums[i],1});
            }
        }
        vector<int> temp;
        dfs(temp,0);
        return res;
    }

    void dfs(vector<int> temp,int now)
    {
        if(now==m)
        {
            res.push_back(temp);
            return;
        }
        for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++)
        {
            if(it->second>0)
            {
                it->second--;
                temp.push_back(it->first);
                dfs(temp,now+1);
                temp.pop_back();
                it->second++;
            }
        }
    }
};

每个位置的候选元素互不相同，应该就没有重复了。

yxc 2019-08-02 12:10 回复了比比多味豆的评论

不错！这种搜索顺序也是可以的~

T-SHLoRk 2019-08-15 14:43 回复了比比多味豆的评论

而且map数据结构内部有序，=可以保证我们的搜索结果也是字典序的

yxc 2019-08-15 14:52 回复了 T-SHLoRk 的评论

要保证字典序的话，可以从搜索顺序入手，如果用map来保证字典序，效率会低一些。

风之羁绊 2019-06-29 14:44

请问如果这道题，要求输出字典序，那应该怎么做？

yxc 2019-06-29 17:42

上面的代码会优先枚举值较小的数字，得到的结果就是按字典序排好序的。

风之羁绊 2019-06-29 23:34 回复了 yxc 的评论

不是字典序的，输入为1,2,3,4的话，上面代码结果返回[[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,4,2,3],[1,3,4,2],[1,4,3,2],[2,1,3,4],[2,1,4,3],[3,1,2,4],[4,1,2,3],[3,1,4,2],[4,1,3,2],[2,3,1,4],[2,4,1,3],[3,2,1,4],[4,2,1,3],[3,4,1,2],[4,3,1,2],[2,3,4,1],[2,4,3,1],[3,2,4,1],[4,2,3,1],[3,4,2,1],[4,3,2,1]]

yxc 2019-07-03 01:57 回复了风之羁绊的评论

啊对，确实不是字典序。可以换一种搜索顺序：从前往后依次枚举每一位填哪个数字，枚举数字的时候从小到大即可。

ljskkljs 2019-06-16 14:06

请问if (u + 1 < nums.size() && nums[u + 1] != nums[u])中，为什么要加u + 1 < nums.size()这个限制条件

yxc 2019-06-16 15:15

当 u + 1 == nums.size() 时，nums[u + 1]` 就越界了。

JJlin 2019-06-06 08:20

如果全排列，再用哈希去掉重复的排列，这样的时空复杂度会大多少？

JJlin 2019-06-06 08:29

想了一下，如果重复的数字太多，那会多出很多额外的计算量

yxc 2019-06-06 10:17

时间复杂度和空间复杂度都是 $O(n \times n!)$ 。

JJlin 2019-06-06 10:45 回复了 yxc 的评论

谢谢你的回复，这个网站太有用了，每天都能学到很多新知识

yxc 2019-06-06 12:28 回复了 JJlin 的评论

加油hh

没事看看星星 2019-04-21 20:56

#### 我认为我的方法看起来好一些

class Solution:
    def permuteUnique(self, nums):
        if not nums:
            return nums
        nums.sort()
        def dfs(nums, index):
            if index == len(nums):
                res.append(path+[])
                # return
            for i in range(len(nums)):
                if i > 0 and nums[i] == nums[i-1] and not visit[i-1]:   # 去重的关键体现处
                    continue
                if not visit[i]:
                    visit[i] = True
                    path.append(nums[i])
                    dfs(nums, index+1)                    
                    path.pop()
                    visit[i] = False

        path = []
        res = []
        visit = [False for _ in range(len(nums))]
        dfs(nums, 0)
        return res