题目：
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:输入: [1,2,3]
输出:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
递归解法：
如示例中的集合{1,2,3}，排列情况有3！=6中排列方法。其第一个元素有3种选择1,2,3，对于第一个元素为1的排列，其第二个元素有2种选择2，3；第一个元素为2的排列，第二个元素也有2种选择1，3；第一个元素为3的排列，第二个元素为1,2两种选择。
class Solution {
public:
void swap(vector<int>& nums,int p,int q)
{
int tmp=nums[p];
nums[p]=nums[q];
nums[q]=tmp;
}
void resove(vector<int> &nums,int n,vector<vector<int>> &result)
{
if(n==nums.size())
{
result.push_back(nums);
return;
}
for(int i=n;i<nums.size();i++)
{
swap(nums,n,i);
resove(nums,n+1,result);
swap(nums,n,i);
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
if(nums.size()<=0) return result;
resove(nums,0,result);
return result;
}
};
字典序解法：
这里先给出算法思想，然后在举例说明：
a.对于排列s[1...n]，找到所有满足s[k]<s k+1 的k的最大
值，如果这样的k不存在，则说明当前排列已经是a的所有排列
中字典序最大者，所有排列输出完毕。
b.在s[k+1...n]中，寻找满足这样条件的元素l，使得在所有a[l]>a[k]
的元素中，s[l]取得最小值。也就是说s[l]>s[k]，但是小于所有其
它大于s[k]的元素。
c.交换s[l]与s[k].
d.对于s[k+1...n]，反转该区间内元素的顺序。也就是说s[k+1]与
s[n]交换，s[k+2]与s[n-1]交换，……，这样就得到了s[1...n]在
字典序中的下一个排列。
示例：s={1,2,3,4,5}开始排列
假设此时序列为：s= {1,3,5,4,2},
经过步骤a,找到k=1,s[k+1]=5;
经过步骤b，找到l=3,s[l]=4;
步骤c，交换则 s[k(1)]=4,s[l(3)]=3,集合s={1,4,5,3,2};
步骤d,翻转则s={1,4,2,3,5}；到此得到下一个排列。
注意：以上举例是特殊情况，此示例开始序列为从小到大的排列的最小排列，如果给出的序列不是最小排列的如{0，-1,1}，则得不出正确结果，因题目是无重复元素，则具体写代码时可以以下标作为排列目标，最后打印时在确定具体元素。具体代码如下:
代码：
class Solution {
public:
//翻转元素
void reverse(vector<int> &nums,int s,int e)
{
for(int i=s;i<e;i++,e--)
{
int tmp=nums[i];
nums[i]=nums[e];
nums[e]=tmp;
}
}
//插入元素，用下标来找具体元素
void pushelement(vector<int> &nums,vector<int> &Index,vector<vector<int>> &result)
{
vector<int> r;
for(int i=0;i<Index.size();i++)
{
r.push_back(nums[Index[i]]);
}
result.push_back(r);
}
//无重复元素，则用下标代表集合，以防出现非有序的元素：如[0,-1,1]
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
if(nums.size()<=0) return result;
vector<int> Index;
for(int i=0;i<nums.size();i++)
{
Index.push_back(i);
}
pushelement(nums,Index,result);
while(true)
{
//寻找最大k值，使得Index[k]<Index[k+1]
int k=Index.size()-1;
bool bexist=false;
for(;k>0;k--)
{
if(Index[k]>Index[k-1])
{
k-=1;
bexist=true;
break;
}
}
if(bexist==false)
{
return result;
}
//寻找最小值l,使得Index[l]>Index[k];
int l=k+1;
int tmp=Index[k+1];
for(int i=k+2;i<Index.size();i++)
{
if(Index[i]>Index[k] && Index[i]<tmp)
{
l=i;
tmp=Index[l];
}
}
//交换Index[k]与Index[l];
tmp=Index[k];
Index[k]=Index[l];
Index[l]=tmp;
//翻转元素
reverse(Index,k+1,Index.size()-1);
pushelement(nums,Index,result);
}
return result;
}
};
题目： 给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例：输入: [1,1,2]
输出:[ [1,1,2],[1,2,1], [2,1,1]]
思路和上述，无重复的排列相同，只是在最开始对数组进行了排序，得到最小排列，另外为了去重： if(Index[i]>Index[k] && Index[i]<tmp) 此处改为 ： if(Index[i]>Index[k] && Index[i]<=tmp)，就能保证得到非重复的元素，其实，无重复的排列也可添加上等号不影响结果，本例这样写只是为了示例。代码如下：
class Solution {
public:
//翻转元素
void reverse(vector<int> &nums,int s,int e)
{
for(int i=s;i<e;i++,e--)
{
int tmp=nums[i];
nums[i]=nums[e];
nums[e]=tmp;
}
}
//无重复元素，则用下标代表集合，以防出现非有序的元素：如[0,-1,1]
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> result;
if(nums.size()<=0) return result;
//排序,得到最小排列
sort(nums.begin(),nums.end());
result.push_back(nums);
while(true)
{
//寻找最大k值，使得nums[k]<nums[k+1]
int k=nums.size()-1;
bool bexist=false;
for(;k>0;k--)
{
if(nums[k]>nums[k-1])
{
k-=1;
bexist=true;
break;
}
}
if(bexist==false)
{
return result;
}
//寻找最小值l,使得nums[l]>numa[k];
int l=k+1;
int tmp=nums[k+1];
for(int i=k+2;i<nums.size();i++)
{
//此处去重，可与无重复数字的全排列作比较，观察条件设置
if(nums[i]>nums[k] && nums[i]<=tmp)
{
l=i;
tmp=nums[l];
}
}
//交换nums[k]与nums[l];
tmp=nums[k];
nums[k]=nums[l];
nums[l]=tmp;
//翻转元素
reverse(nums,k+1,nums.size()-1);
result.push_back(nums);
}
return result;
}
};
网友评论