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.
class Solution {
public:
string getPermutation(int n, int k) {
string result;
bool used[];
memset(used, false, );
int base[];
base[] = ;
for (int i = ; i <= n; ++i) {
base[i] = base[i - ] * i;
}
--k;
for (int i = ; i < n; ++i) {
int p = k / base[n - - i];
for (int j = ; j <= n; ++j) {
if (!used[j] && p-- == ) {
result.push_back('' + j);
used[j] = true;
break;
}
}
k %= base[n - - i];
}
return result;
}
};
n个数组的全排列中,以1开头的个数(n-1)!个,同样以2..n开头的个数有(n-1)!个,这样根据(k-1)/[(n-1)!]可知第一个数是多少,依次类推...