Description
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.
思路
- 分析，n个数的排列一共有n!个，
- 其中分别以1,2,...,n-1开头的各有(n-1)!种
- 所以，index = (k - 1) / ((n-1)!)为第一个开头的数字
- 然后k = k - index * (n-1)! 为剩下的第几个
- 然后重复计算剩下的(n-1)个数字即可。
代码
class Solution {
public:
string getPermutation(int n, int k) {
string res;
vector<char> vec;
int sum = 1;
for(int i = 0; i < n; ++i){
vec.push_back('1' + i);
sum *= (i + 1);
}
int index = 0;
int i = 0, tmp = 0;
while(n > 0){
tmp = sum / n;
index = (k - 1) / tmp;
res += vec[index];
k = k - index * tmp;
sum /= n;
n--;
}
return res;
}
};内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
