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 解题报告 中的算法搞一下就好了。。
1/* ***********************************************
2Author :111qqz
3Created Time :2017年04月13日 星期四 15时17分19秒
4File Name :60.cpp
5************************************************ */
6class Solution {
public:
1 void solve(vector<int>&nums)
2 {
3 int n = nums.size();
4 if (n==0) return;
5 int k = -1;
6 for ( int i = n-2 ; i>= 0 ; i--)
7 {
8 if (nums[i]<nums[i+1])
9 {
10 k = i;
11 break;
12 }
13 }
14 if (k==-1)
15 {
16 reverse(nums.begin(),nums.end());
17 return;
18 }
19 int l = -1;
20 for ( int i = n-1 ; i > k ; i--)
21 {
22 if (nums[k]<nums[i])
23 {
24 l = i ;
25 break;
26 }
27 }
28 swap(nums[l],nums[k]);
29 reverse(nums.begin()+k+1,nums.end());
30 }
31 string getPermutation(int n, int k) {
32 vector<int>nums;
for ( int i = 1 ; i <= n ; i++) nums.push_back(i);
for ( int i = 2 ; i <= k ; i++) solve(nums);
1 string res = "";
2 int siz = nums.size();
3 for ( int i = 0 ; i < siz ; i++) res = res + char(nums[i]+'0');
4 return res;
}
};