Leetcode 60 Permutation Sequence
来源:程序员人生 发布时间:2016-09-30 11:06:45 阅读次数:2456次
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的数字串字典序的第K个串。
每位定下来以后,后面共有(n⑴)!个排列,应用这个特点反复减k,让k去逼近1。
class Solution {
public:
string getPermutation(int n, int k) {
int mp[10];
mp[0]=mp[1]=1;
vector<int> v(1,1);
for(int i=2;i<10;i++)
{
mp[i]=mp[i⑴]*i;
v.push_back(i);
}
string result;
while(n--)
{
vector<int>::iterator it=v.begin();
while(k>mp[n])
{
k-=mp[n];
it++;
}
result+=('0'+*it);
v.erase(it);
}
return result;
}
};
生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠