牛客网：全排列

目录

1.没有重复数字的全排列

2.有重复数字的全排列

暴力

1.没有重复数字的全排列

 我们其实也可以用next_permutation这个接口，但是总不如自己写的有意思

首先，这里的字典序，我也不知道答案怎么实现的，官网给出的答案貌似是根本没有考虑的。

所以我们在这里也随便乱序输出。

我们设置一个函数，这个函数表示现在第k位以前的数字已经不会移动，我们要改变的是位置>=k之后的数字之间的位置关系。因此要传入一个索引位置作为参数，一个答案的引用用来填写答案，以及一个原来的数组引用。

至于思路，我们就是暴力完事，当然用递归实现：

对于ABC这样一个序列

首先ABC本身就是一个答案之一，这也是为什么=k取到的原因，=k表示的是自己和自己交换即当前位置不交换。

接下来说点要交换的，比如我们拿A依次和后面的所有元素交换，例如与B，变成BAC，接下来我们就忽略第一位，只看AC，这个AC有AC和CA两种排列方法，其实意思是A与后面的元素换或不换的两种情况。

那么我们提取思路就是：

对于一个序列A...，A的位置不变或者和后面的所有元素交换依次，然后在A交换完后切换到下一个位置的元素进行相同的操作，这不就是递归么。

代码如下所示：

class Solution {
public:
    void permuteCore(vector> &res,vector &num, int k){
        if(k==num.size()-1){
            res.push_back(num);
            return;
        }
        for(int i=k;i > permute(vector &num) {
        sort(num.begin(), num.end());
        vector> res;
        permuteCore(res, num, 0);
        return res;
    }
};

这里要注意回溯的细节。

其次，每个元素循环的次数是n-k，n是总长度,k是下标位置，k=0，1...n，所以时间复杂度是O(n!)

2.有重复数字的全排列

这个时候有重复数字，如果我们还是一样来交换的话，需要用到集合来做数据结构。

我们这里有两种方法，用集合（交换），和暴力。

暴力

本质上求取一个全排列其实是决定数字的放置位置，比如第一个位置放第几个数，第二个位置放第几个数。因此，我们可以用一个visit数组来记录，我们之前已经放置了哪些位置的数字。

之后我们要解决重复的问题，比如我们第1个位置放了2，整个数组里面有两个2，我们如何避免重复？

首先将数组进行排序，这样很清楚哪些数重复了，其实就是那些num[i-1]==num[i]的数字。

决定第k个位置是否放置数字num[i]的思路如下：

1.如果visit[i]=1说明该位置已经在前面的递归中放过，可以直接看下一个数

2.如果出现两个数字相邻且前面那个数字visit[i]=0说明已经在前面放过，那么直接跳过当前数，否则就会出现重复的情况

代码如下所示：

class Solution {
public:
    void permuteUniqueCore(vector> &res, vector &num, vector &tmp, vector &visit){
        if(tmp.size()==num.size()){
            res.push_back(tmp);
            return;
        }
        for(int i=0;i0 && num[i-1]==num[i] && !visit[i-1])){
                continue;
            }
            visit[i]=1;
            tmp.push_back(num[i]);
            permuteUniqueCore(res, num, tmp, visit);
            visit[i]=0;
            tmp.pop_back();
        }
    }
    
    vector > permuteUnique(vector &num) {
        sort(num.begin(), num.end());
        vector> res;
        vector tmp;
        vector visit(num.size(), 0);
        permuteUniqueCore(res, num, tmp, visit);
        return res;
    }
};

集合

之前说过如果直接在原数组上交换的话，直接用集合来存储就好了，代码如下所示：

#include 
#include 
#include 
using namespace std;
class Solution {
public:
    void permuteUniqueCore(set> &st, vector &num, int k){
        if(k==num.size()){
            st.insert(num);
            return;
        }
        for(int i=k;i > permuteUnique(vector &num) {
        set> st;
        sort(num.begin(), num.end());
        vector tmp;
        permuteUniqueCore(st, num, 0);
        vector> res;
        for(auto vec : st){
            res.push_back(vec);
        }
        return res;
    }
};

next_permutation接口

当然，还有一个神奇的接口可以调用，那就是next_permutation，这个接口就是喂给他一个序列然后他会给你下一个刚好大一点的排列序列，写法如下所示：

using namespace std;
class Solution {
public:    
    vector > permuteUnique(vector &num) {
        sort(num.begin(), num.end());
        vector> res;
        res.push_back(num);
        while(next_permutation(num.begin(), num.end())){
            res.push_back(num);
        }
        return res;
    }
};

我们也可以自己手写一个permutation:

    bool next_Permutation_Own(vector &num){
        int i=num.size()-2;
        //从倒数第二个元素往前找到第一个元素
        //这个元素比其后面的那个元素要小
        //或者直到第一个
        while(i>=0 && num[i] >= num[i+1]){
            i--;
        }
        int j=num.size()-1;
        //从最后一个元素向前找第一个大于位置i的元素的元素位置
        while(j>=0 && num[i]>=num[j]){
            j--;
        }
        swap(num[i], num[j]);
        reverse(num.begin()+i+1, num.end());
        return true;
    }

思路是这样的：

从后往前找到第一个非递增元素的位置，从后往前找到第一个大于这个元素的另外一个元素的位置，这样交换后就比刚才的大了一点，至于为什么要reverse一下，因为reverse之后更小了，我只能这么理解，至于怎么证的属实不懂。