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

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.

思路：还是根据leetcode 31 解题报告 中的算法搞一下就好了。。

/* ***********************************************
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;

    }

};