题目描述:(链接)
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):
"123""132""213""231""312""321"
Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
解题思路:
按照上一题的思路，暴力破解，超时了，k可以超过n!，冏！代码如下，代码折叠，别打开：
class Solution {
public:
string getPermutation(int n, int k) {
string result(n, ‘0‘);
for (size_t i = 0; i < result.size(); ++i) {
result[i] += i + 1;
}
for (size_t i = 0; i < k; ++i) {
nextPermutation(result);
}
return result;
}
void nextPermutation(string& str) {
int i;
int j;
// From right to left, find the first item(PartitionNumber) which violates the increase trend
for (i = str.size() - 2; i >= 0; --i) {
if (str[i] < str[i + 1]) break;
}
// From right to left, find the first item(ChangeNumber) which is larger than PartitionNumber
for (j = str.size(); j >= i; --j) {
if (str[j] > str[i]) break;
}
// swap PartitionNumber and ChangeNumber
if (i >= 0) {
swap(str[i], str[j]);
}
// reverse all after PartitionNumber index
reverse(str.begin() + i + 1, str.end());
}
};
[LeetCode]Permutation Sequence
原文：http://www.cnblogs.com/skycore/p/4858753.html