首页 > 代码库 > leetcode 刷题之路 77 Permutations II

leetcode 刷题之路 77 Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:

[1,1,2][1,2,1], and [2,1,1].

Permutations 的升级版,依旧是全排列问题,但是序列中可能会出现重复数字

思路:采用字典序的非递归方法。从字典顺序最小的一种排列开始,每次获得字典序刚好比前一个排列大的排列,直到得到字典序最大的排列时,就得到了所有的结果,以字符串"abc"为例,"abc"是字典序最小的排列,所有情况按字典序排列为"abc","acb","bac","bca","cba","cab"。

具体步骤为为:
1.字符串进行排序,得到字符串的最小字典序排列(C0C1C2...Cn),Ci<=Ci+1。  
2.从后往前,找到一对相邻的升序元素CiCi+1,(Ci<Ci+1),如果遍历完字符串找不到这样的相邻升序对,说明已经达到了字典序最大的全排列
3.从字符串结束位置到位置i遍历,找到比Ci大的元素Cj,交换Cj的位置
4.将Ci+1到Cn所有的字符逆序,这样得到的排列刚好比之前的字典序大(因为转换后Ci+1<Ci+2<...<Cn,为最小字典序)。
5.重复3,4,5过程直到字典序最大。

AC code:

class Solution {
public:
    void swap(int &i,int &j)
    {
        int temp=i;
        i=j;
        j=temp;
    }
    vector<vector<int> > permuteUnique(vector<int> &num) 
    {
        vector<vector<int>> res;
        int i,j,n=num.size();
        sort(num.begin(),num.end());
        res.push_back(num);
        while(true)
        {
            for(i=n-2;i>=0;i--)
                if(num[i]<num[i+1])
                    break;
            if(i<=-1)
                return res;
            for(j=n-1;j>i;j--)
                if(num[j]>num[i])
                    break;
            swap(num[i],num[j]);
            for(int k=i+1;k<(i+1+n)/2;k++)
                swap(num[k],num[n-(k-i)]);
            res.push_back(num);
        }
    }
};