Note: This article is available in Chinese only. 本文暂无英文版本。
View original
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 解题报告 中的算法搞一下就好了。。
1/* ***********************************************
2Author :111qqz
3Created Time :2017年04月13日 星期四 15时17分19秒
4File Name :60.cpp
5************************************************ */
6class Solution {
7
8public:
9
10 void solve(vector<int>&nums)
11 {
12 int n = nums.size();
13 if (n==0) return;
14 int k = -1;
15 for ( int i = n-2 ; i>= 0 ; i--)
16 {
17 if (nums[i]<nums[i+1])
18 {
19 k = i;
20 break;
21 }
22 }
23 if (k==-1)
24 {
25 reverse(nums.begin(),nums.end());
26 return;
27 }
28 int l = -1;
29 for ( int i = n-1 ; i > k ; i--)
30 {
31 if (nums[k]<nums[i])
32 {
33 l = i ;
34 break;
35 }
36 }
37 swap(nums[l],nums[k]);
38 reverse(nums.begin()+k+1,nums.end());
39 }
40 string getPermutation(int n, int k) {
41 vector<int>nums;
42
43 for ( int i = 1 ; i <= n ; i++) nums.push_back(i);
44 for ( int i = 2 ; i <= k ; i++) solve(nums);
45
46 string res = "";
47 int siz = nums.size();
48 for ( int i = 0 ; i < siz ; i++) res = res + char(nums[i]+'0');
49 return res;
50
51 }
52
53};