问题
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.
例子
n = 3, k = 4
"231"
分析
设n = 4，根据第一位数字的不同，可以将所有排列分成如下四种类型：
1xxx
2xxx
3xxx
4xxx
每种类型的数量为3!。当然，我们也可以把每种类型再根据第二位数字的不同进行细分，例如3XXX可以分为31XX，32XX，34XX三类，每类的数量为2!。
现假设要求第k=22个排列。由于习惯从0开始数，即第21个排列。21/3!=6...3，可以确定该序列的第一个数字为4；3/2!=1...1，可以确定第二个数字为2，1/1!=1...0，可以确定第三个数字为3；0/0!=0...0，可以确定第四个数字为1。因此第22个排列为4231。
要点
逐位求出第k个排列的数字。
时间复杂度
O(n)
空间复杂度
O(1)
代码
class Solution {
public:
string getPermutation(int n, int k) {
string res(n, '0');
int fact = 1;
for (int i = 1; i <= n; ++i) {
res[i - 1] += i;
fact *= i;
}
k--;
auto first = res.begin();
for (; n > 0; --n, ++first) {
fact /= n;
auto cur = first + k / fact;
// 将cur移到排列的首部
rotate(first, cur, cur + 1);
k %= fact;
}
return res;
}
};
