Permutation Sequence--LeetCode

梦里梦外; 2022-08-07 11:46 27阅读 0赞

# 题目： #

The set `[1,2,3,…,n]` contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,  
We get the following sequence (ie, for n = 3):

1.  `"123"`
2.  `"132"`
3.  `"213"`
4.  `"231"`
5.  `"312"`
6.  `"321"`

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

思路：使用STL中的思路，从后往前找一对相邻的数，在一对相邻的数中第一个元素小于第二个元素，记做\*i<\*ii，从后往前找到第一个元素\*j，是的\*j>\*i，然后交换\*i和\*j，然后交换从\*II开始（包含\*ii在内）到数组末尾的序列。

#include <iostream>
    #include <vector>
    
    using namespace std;
    /*STL中的permutation 
    从后往前找一对相邻数字 前者比后者大 
    重新重后往前找一个比这一对数的第一个数大的数，
    交换这两个数 然后反转上述找到的一对数中第二个元素开始之后的序列 
    */
    
    void Rserve(vector<int>& vec,int begin,int end)
    {
    	while(begin <= end)
    	{
    		swap(vec[begin],vec[end]);
    		begin++;
    		end--;
    	}
    } 
    
    bool FindPair(vector<int>& vec,int& first,int& second)
    {
    	int last = vec.size()-1;
    	for(;last>0;last--)
    	{
    		second = last;
    		first = last-1;
    		if(vec[first] < vec[second])
    			return true;
    	}
    	return false;
    }
    
    bool next_premutation(vector<int>& vec)
    {
    	int first,second,index;
    	if(FindPair(vec,first,second))
    	{
    		index = vec.size()-1;
    		for(;index>=first;index--)
    		{
    			if(vec[index] > vec[first])
    				break;
    		}
    		swap(vec[index],vec[first]);
    		Rserve(vec,second,vec.size()-1);
    		return true;
    	}
    	return false;
    }
    
    int main()
    {
    	vector<int> vec(3);
    	int i;
    	for(i=0;i<vec.size();i++)
    		vec[i] = i+1;
    	vec[1]	=1;
    	do{
    		int i;
    		for(i=0;i<vec.size();i++)
    			cout<<vec[i]<<" ";
    		cout<<endl; 
    	}while(next_premutation(vec));
    	return 0;
    }