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

题意分析

• 给你一个序列，需要先将这个序列的相同的元素去掉，也就是先去重。然后按照原来的序列进行一个全排列，需要对每个排列进行字典序排列。

• 前置知识

  • 我们按照顺序来。
  • 首先，你需要知道怎么去重，在C++里面，对数组的去重两种方法，一种是自己实现，先对整个数组进行排序，然后两两相邻的进行比较。一旦出现不同就放入集合里面。另一种是使用C++的库函数unique。其实差别不大。
  • 然后，我们说一下什么是全排列。全排列就是给你若干个数字，将这些数字混乱排列得到的所有的结果。
  • 最后，我们来说一下什么是字典序。就是按照ASCII表里面出现的顺序，从小到大输出。比如，两个字符串abc,abb，显然，对于前两个字符，都是一样的，比较不出来，但是第三个字符明显后者比前者更小。所以后者的字典序更小。这也是大多数字符串排序算法实现的基本原理。

思路分析

解法一 C++库函数

• 首先，我们来说一个简单的，就是称为调库工程师。我们直接利用C++为我们实现好的库函数进行全排列。也就是，我们使用next_permutation函数。具体这个函数的实现可以自己先百度进行了解。然后，我们先利用unqiue去重。之后就可以直接用啦！

• 代码如下

  • 根据数学上面的知识，全排列的时间复杂度为O(n!)
  • 除了结果数组和参数，只使用了少数变量，空间复杂度为O(1)

class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        // 特判为空的情况
        vector<vector<int> > ans;
        if(!num.size()){
            return ans;
        }
        sort(num.begin(),num.end());
        // 利用C++的库函数进行处理
        do{
            ans.push_back(num);
        }while(next_permutation(num.begin(),num.end()));

        return ans;
    }
};

解法二 DFS回溯算法

• 显然，如果想真正学习算法的人肯定不会止步于上一次，为什么我们不自己实现呢？对了，学习阶段还是需要自己多动手实现。于是，我们可以自己利用DFS回溯算法求全排列。我们先利用二叉树的DFS回溯来帮助大家了解什么是回溯算法吧，其实题的实现远远比二叉树的要简单。

• 而在本题目中，我们只需要在遍历的时候标记那些访问过的点，对于没有访问过的点，我们继续向下递归，然后标记上，在递归结束返回之后，我们需要做的是把标记清楚。依次进行处理。这样，我们每个结点的位置在任何的位置都有可能，也就是实现了全排列的情况。

• 代码如下

  • 根据数学上面的知识，全排列的时间复杂度为O(n!)
  • 使用了一个unordered_map类型的vis进行标记，空间复杂度为O(n)

class Solution {
public:
    vector<vector<int> > ans;
    unordered_map<int,bool> vis;
    void dfs(int cnt,int n,vector<int>& num,vector<int>& tmp){
        // 递归边界
        if(cnt==n){
            ans.push_back(tmp);
            return;
        }
        for(auto x:num){
            if(!vis[x]){
                // 如果这个元素没有被访问，那么进行访问
                vis[x]=true;
                tmp.push_back(x);
                dfs(cnt+1,n,num,tmp);
                // 访问完之后进行回溯
                tmp.pop_back();
                vis[x]=false;
            }
        }
    }
    vector<vector<int> > permute(vector<int> &num) {
        // 特判为空的情况
        if(!num.size()){
            return ans;
        }
        sort(num.begin(),num.end());
        // 进行DFS回溯求解
        vector<int> tmp;
        dfs(0,num.size(),num,tmp);
        return ans;
    }
};