【LeetCode】46. Permutations 的两种解法及注释、分析

た入场券 2022-07-26 01:42 130阅读 0赞

**46. Permutations **

Given a collection of **distinct** numbers, return all possible permutations.  
  
For example,  
\[1,2,3\] have the following permutations:

\[1,2,3\], \[1,3,2\], \[2,1,3\], \[2,3,1\], \[3,1,2\], and \[3,2,1\].

【分析】

实现全排列，一般有两种思路，一是“递归”，一是类似【LeetCode】31题的[NextPermutation的方法][NextPermutation]。由于本题已经说明给定数据集中不存在重复的数字，因此，递归不失为一个好的思路，但是也有缺点，那就是空间消耗比较大，网上大牛写了一个很简洁的[递归版程序][Link 1]（Java）,我根据他的版本写了一个C++版的。另外，采用NextPermutation比较直观，即便给定数据集中存在重复数字(【LeetCode 47.Permutations II】)，依然具备较好的鲁棒性，但递归版则需要修改。

【方法一：基于NextPermutation】

**根据该方法的原理：**

如果输入为\[1,2,3\]，输出依次为：\[1,2,3\]，\[1,3,2\]，\[2,1,3\]，\[2,3,1\]，\[3,1,2\]，\[3,2,1\]依次增大

class Solution
    {
    public:
    	vector<vector<int>> permute(vector<int>& nums)
    	{
    		bool endflag=false;
    		inputNums=nums;
    		sort(inputNums.begin(),inputNums.end());//输入数据进行升序排列
    
    		result.push_back(inputNums);//初始排序构成最小数，存入结果容器
    		while(!endflag)//从小到大依次组合数字，直到构成最大数循环结束
    		{
    		   endflag=searchPermute(inputNums);
    		   if(!endflag)//避免多次存储
    		   result.push_back(inputNums);//依次将组合存入结果容器
    		}
    		return result;
    	}
    private:
    	vector<int> inputNums;
    	vector<vector<int>> result;
    
    	bool searchPermute(vector<int>& currentPermute)
    	{
    		int keypoint;//降序关键点下标
    		bool end=false;//判断当前排列是否构成最大数
    		keypoint=currentPermute.size()-1;//从末端开始搜索
    		while(keypoint>0&¤tPermute[keypoint]<=currentPermute[keypoint-1])//“<=”条件可以cover给定数据存在重复的情况
    			keypoint--;//遍历找到降序关键点
    		if(keypoint==0)//关键点为零，则当前排列构成最大数，我们从最小数开始构造，到最大数结束
    		{
    			end=true;
    		}
    		else
    		{
    			int minNum=currentPermute[keypoint-1];//降序关键点前待替换数字
    			for(int i=currentPermute.size()-1;i>keypoint-1;i--)//在降序关键点后面的数字中寻找最小的比待替换数字大的数
    			{
    				if(minNum<currentPermute[i])//找到则进行替换
    				{
    					int temp;
    					temp=currentPermute[i];
    					currentPermute[i]=currentPermute[keypoint-1];
    					currentPermute[keypoint-1]=temp;
    					break;
    				}
    			}
    			sort(currentPermute.begin()+keypoint,currentPermute.end());//替换后，将关键点后面的数字升序排列，形成局部最小
    		}
    		return end;//返回
    	}
    
    };

**【方法二：递归版】**

**根据该方法的原理：**

如果输入为\[1,3,2\]，输出依次为：\[1,3,2\]，\[1,2,3\]，\[3,1,2\]，\[3,2,1\]，\[2,1,3\]，\[2,3,1\]依次增大

class Solution
    {
    public:
    	vector<vector<int>> permute(vector<int>& nums)
    	{
    		vector<vector<int>> result;//存储各种排列结果
    		vector<bool> used(nums.size(),false);//标记元素是否已被使用
    		vector<int> temp;//存储当前排列
    		if(nums.size()==0)return result;//输入数据为空直接返回
    		searchPermute(nums,temp,result,used);//调用排列函数
    		return  result;	
    	}
    	
    	void searchPermute(vector<int>& nums,vector<int>& temp,vector<vector<int>>& result, vector<bool>& used)
    	{
    		if(temp.size()==nums.size())//如果当前排列已满（输入数据均用到）
    		{
    			result.push_back(temp);//将当前排列存入结果容器
    			return;
    		}
    		else
    		{
    			for(int i=0;i<nums.size();i++)//循环排列
    			{
    				if(!used[i])//如果输入数据尚未列入排列
    				{
    					used[i]=true;//标记该数据已被列入当前排列
    					temp.push_back(nums[i]);//将该数据列入当前排列
    					searchPermute(nums,temp,result,used);//递归调用，直到最后一个元素列入，逐层返回
    					temp.pop_back();//移除当前容器顶部数据
    					used[i]=false;//标记被移除数据为未被使用状态
    				}
    			}
    		}
    
    	}
    };

[NextPermutation]: http://blog.csdn.net/jin_kwok/article/details/51024219
[Link 1]: http://blog.csdn.net/linhuanmars/article/details/21569031