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

题意分析

• 首先，题目给出一个大小为n的数组，然后，需要我们求出这个数组的全排列。但是要注意的是这个数组里面可能存在相同的数字。

思路分析

解法一 库函数实现

• 学习过C++的同学应该都直到，C++有一个库函数next_permutation可以用来处理数组的全排列问题，但是这个库函数需要我们先对这个数组进行升序排序。具体我们来看一下源码。

template<class _BidIt> inline
bool _Next_permutation(_BidIt _First, _BidIt _Last)
{ // permute and test for pure ascending, using operator<

//-----------------------------------------------\
_DEBUG_RANGE(_First, _Last);
_BidIt _Next = _Last;
if (_First == _Last || _First == --_Next)
   return (false);

//检查边界

//-----------------------------------------------/

// 我们看到，这里写了一个空循环
for (; ; )
   { // find rightmost element smaller than successor
   _BidIt _Next1 = _Next;
   if (_DEBUG_LT(*--_Next, *_Next1))
    { // swap with rightmost element that's smaller, flip suffix
    _BidIt _Mid = _Last;
    for (; !_DEBUG_LT(*_Next, *--_Mid); )
     ;
    std::iter_swap(_Next, _Mid);

//从右往左找到相邻的两个，右边比左边大，左边那个就是需要被替换的，然后从右边找到一个比这个元素大的，交换这两个元素的位置
    std::reverse(_Next1, _Last);

// 交换之后，翻转交换元素的后面的所有元素
    return (true);
    }

   if (_Next == _First)
    { // pure descending, flip all
    std::reverse(_First, _Last);
    return (false);
    }
   }
}

• 具体请看代码
  • 需要进行全排列，根据数学中排列组合的知识，全排列的时间复杂度为O(n!)
  • 除了参数和结果数组基本没有使用其余变量，空间复杂度为O(1)

class Solution {
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int> > ans;
        sort(num.begin(),num.end()); // 注意，全排列需要先对数组进行升序排列
        do{
            ans.push_back(num);
            // 利用C++的库函数进行遍历所有的排列
        }while(next_permutation(num.begin(), num.end()));
        return ans;
    }
};

• 最后说一句，如果是为了学习算法，还是不要偷懒，最好还是自己可以实现这个功能，不然注定只是一名调库工程师。所以我们下面来为大家介绍如何利用DFS的回溯解决这个问题。

解法二 回溯法

• 首先，我默认大家都已经了解了深度优先搜索的基础知识。如果有不了解的，请看这个传送门.
• 然后，我给大家回一个图帮助大家更好地理解什么是回溯？
  

其实就类似于我们日常的撤回功能，我们在进行某一种行为的时候这个状态改变了，但是我们发现这个行为是错误的，我们就需要进行撤回操作，恢复执行这个行为之前的状态。当然，真正的回溯其实远不是如此，这个只是帮助大家理解。

• 好了，我们接下来说一下DFS操作，递归参数为遍历到的数字，递归出口为数字到了num数组的大小，然后就是遍历数组，我们需要对没有被遍历到的数字执行递归操作，递归前需要将这个位置标记为访问了，同时存入，递归出来后需要将这个位置重新标记为未访问，然后之前存入的数字弹出。最后记得给得到的序列去重即可。

• 代码如下

  • 全排列的时间复杂度未O(n!)
  • 使用了unordered_map和一些中间的vector进行处理，空间复杂度为O(n)

class Solution {
public:
    unordered_map<int,bool> mp;
    vector<vector<int> > ans;
    vector<int> tmp,now;
    int len;
    void dfs(int cnt){  // cnt表示当前遍历到的数字的个数
        if(cnt==len+1){ // 递归出口
            ans.push_back(now);
            return;
        }

        for(int i=0;i<len;i++){
            if(mp[i]==0){
                // 如果这个数字没有被访问，先将这个数字放到数组里面
                now.push_back(tmp[i]); 
                mp[i]=1; // 然后进行标记
                dfs(cnt+1);
                mp[i]=0;  // 进行回溯
                now.pop_back();
            }
        }
    }
    vector<vector<int> > permuteUnique(vector<int> &num) {
        tmp=num;
        len=num.size();
        dfs(1);
        // 可能存在重复的数字，所以需要进行去重处理
        vector<vector<int> > res;
        sort(ans.begin(),ans.end());
        int m=unique(ans.begin(),ans.end())-ans.begin();
        for(int i=0;i<m;i++){
            res.push_back(ans[i]);
        }
        return res;
    }
};