首页 > 代码库 > Permutations II

Permutations II

2024-08-05 11:33:52   215人阅读

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非常类似，唯一的区别就是在这个题目中元素集合可以出现重复。这给我们带来一个问题就是如果不对重复元素加以区别，那么类似于{1,1,2}这样的例子我们会有重复结果出现。那么如何避免这种重复呢？方法就是对于重复的元素循环时跳过递归函数的调用，只对第一个未被使用的进行递归，我们那么这一次结果会出现在第一个的递归函数结果中，而后面重复的会被略过。如果第一个重复元素前面的元素还没在当前结果中，那么我们不需要进行递归（直接continue）。想明白了这一点，代码其实很好修改。首先我们要对元素集合排序，从而让重复元素相邻，接下来就是一行代码对于重复元素和前面元素使用情况的判断即可。

 

C++实现代码：

#include<iostream>#include<vector>#include<algorithm>#include<cstring>using namespace std;class Solution{public:    vector<vector<int> > permuteUnique(vector<int> &num)    {        vector<vector<int> > ret;        vector<int> path;        int n=num.size();        sort(num.begin(),num.end());        bool visited[n];        memset(visited,false,sizeof(visited));        helper(num,visited,ret,path);        return ret;    }    void helper(vector<int> &num,bool visited[],vector<vector<int> > &ret,vector<int> &path)    {        if(path.size()==num.size())        {            ret.push_back(path);            return;        }        int i;        for(i=0; i<num.size(); i++)        {            if(i>0&&num[i-1]==num[i]&&!visited[i-1])                continue;            if(!visited[i])            {                visited[i]=true;                path.push_back(num[i]);                helper(num,visited,ret,path);                path.pop_back();                visited[i]=false;            }        }    }};int main(){    Solution s;    vector<int> vec= {3,3,0,0,2,3,2};    vector<vector<int> > result=s.permuteUnique(vec);    for(auto a:result)    {        for(auto v:a)            cout<<v<<" ";        cout<<endl;    }    cout<<result.size()<<endl;}

 

不是用回溯实现的，但是不知道原因，为什么通不过？

#include<iostream>#include<vector>using namespace std;class Solution{public:    vector<vector<int> > permuteUnique(vector<int> &num)    {        if(num.empty())            return vector<vector<int> >();        vector<vector<int> > ret {{num[0]}};        size_t i,j,k;        for(i=1; i<num.size(); i++)        {            vector<int> temp1;            vector<vector<int> > temp2=ret;            ret.clear();            for(j=0; j<temp2.size(); j++)            {                temp1=temp2[j];                k=0;                size_t ii;                while((temp1.begin()+k)!=temp1.end())                {                    temp1.insert(temp1.begin()+k,num[i]);                    for(ii=0; ii<ret.size(); ii++)                    {                        if(ret[ii]==temp1)                            break;                    }                    if(ii>=ret.size())                        ret.push_back(temp1);                    temp1=temp2[j];                    k++;                }                temp1.push_back(num[i]);                for(ii=0; ii<ret.size(); ii++)                {                    if(ret[ii]==temp1)                        break;                }                if(ii>=ret.size())                    ret.push_back(temp1);            }        }        return ret;    }};int main(){    Solution s;    vector<int> vec= {3,3,0,0,2,3,2};    vector<vector<int> > result=s.permuteUnique(vec);    for(auto a:result)    {        for(auto v:a)            cout<<v<<" ";        cout<<endl;    }    cout<<result.size()<<endl;}

 

Permutations II


联系
我们