题目描述

输入一组数字（可能包含重复数字），输出其所有的排列方式。

样例

输入：[1,2,3]

输出：
      [
        [1,2,3],
        [1,3,2],
        [2,1,3],
        [2,3,1],
        [3,1,2],
        [3,2,1]
      ]

算法

(next_permutation) $O(n^2)$

C++可以调用库函数next_permutation()，但是这样太简单了，AcWing绝对不会允许的。所以，我们自己实现一个next_permutation！

解题算法：

C++ 代码

class Solution {
public:
    vector<int>reverse(vector<int>nums,int l,int r){
        while(l<r){
            swap(nums[l],nums[r]);
            l++;
            r--;
        }
        return nums;
    }
    vector<int>nextPermutation(vector<int>nums){
        int right=nums.size()-1;
        while(right-1>=0&&nums[right]<=nums[right-1])right--;
        if(right==0)return reverse(nums,0,nums.size()-1);
        int privot=right-1,successor=0;
        for(int i=nums.size()-1;i>privot;i--)
            if(nums[i]>nums[privot]){
                successor=i;
                break;
            }
        swap(nums[privot],nums[successor]);
        return reverse(nums,privot+1,nums.size()-1);
    }
    vector<vector<int>> permutation(vector<int>& nums) {
        vector<vector<int> >res;
        vector<int>tmp=nums;
        bool hh=true;
        while(hh){
            res.push_back(tmp);
            tmp=nextPermutation(tmp);
            if(tmp==nums)hh=false;
        }
        return res;
    }
};

Go 代码

var res[][]int
func reverse(nums[]int,l int,r int){
    for l<r{
        nums[l],nums[r]=nums[r],nums[l]
        l++
        r--
    }
}
func nextPermutation(nums[]int)[]int{
    right:=len(nums)-1
    for right-1>=0&&nums[right]<=nums[right-1]{
        right--
    }
    if right==0{
        reverse(nums,0,len(nums)-1)
        return nums
    }
    privot,successor:=right-1,0
    for i:=len(nums)-1;i>privot;i--{
        if nums[i]>nums[privot]{
            successor=i
            break
        }
    }
    nums[privot],nums[successor]=nums[successor],nums[privot]
    reverse(nums,privot+1,len(nums)-1)
    return nums
}
func judge(x[]int,y[]int)bool{
    for i:=0;i<len(x);i++{
        if(x[i]!=y[i]){
            return false
        }
    }
    return true
}
func add(x[]int){
    tmp:=[]int{}
    for _,v:=range x{
        tmp=append(tmp,v)
    }
    res=append(res,tmp)
}
func permutation(nums []int) [][]int {
    tmp:=[]int{}
    for _,v:=range nums{
        tmp=append(tmp,v)
    }
    for true{
        add(tmp)
        nextPermutation(tmp)
        if judge(tmp,nums){
            break
        }
    }
    return res
}