# leetcode 60. Permutation Sequence (求第k个排列)

Posted by 111qqz on Thursday, April 13, 2017

## TOC

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 _k_th permutation sequence.

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

``````/* ***********************************************
Author :111qqz
Created Time :2017年04月13日 星期四 15时17分19秒
File Name :60.cpp
************************************************ */
class Solution {

public:

void solve(vector<int>&nums)
{
int n = nums.size();
if (n==0) return;
int k = -1;
for ( int i = n-2 ; i>= 0 ; i--)
{
if (nums[i]<nums[i+1])
{
k =  i;
break;
}
}
if (k==-1)
{
reverse(nums.begin(),nums.end());
return;
}
int l = -1;
for ( int i = n-1 ; i > k ; i--)
{
if (nums[k]<nums[i])
{
l = i ;
break;
}
}
swap(nums[l],nums[k]);
reverse(nums.begin()+k+1,nums.end());
}
string getPermutation(int n, int k) {
vector<int>nums;

for ( int i = 1 ; i <= n ; i++) nums.push_back(i);
for ( int i = 2 ; i <= k ; i++) solve(nums);

string res = "";
int siz = nums.size();
for ( int i = 0 ; i < siz ; i++) res = res + char(nums[i]+'0');
return res;

}

};
``````

「真诚赞赏，手留余香」