首页 > 代码库 > Permutation Sequence
Permutation Sequence
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 {
private:
inline int perm(int n)
{
int a=1;
for(int i=1;i<=n;i++)
a*=i;
return a;
}
public:
string getPermutation(int n, int k)
{
int* num=new int[n];
for(int i=0;i<n;i++)
num[i]=i+1;
int dep=1;
string s="";
while(dep<=n)
{
int small=1;
int part=perm(n-dep);
while(k>part)
{
k=k-part;
small++;
}
s=s+char(num[small-1]+‘0‘);
for(int i=small-1;i<n-dep;i++) num[i]=num[i+1];
dep++;
}
return s;
}
};
private:
inline int perm(int n)
{
int a=1;
for(int i=1;i<=n;i++)
a*=i;
return a;
}
public:
string getPermutation(int n, int k)
{
int* num=new int[n];
for(int i=0;i<n;i++)
num[i]=i+1;
int dep=1;
string s="";
while(dep<=n)
{
int small=1;
int part=perm(n-dep);
while(k>part)
{
k=k-part;
small++;
}
s=s+char(num[small-1]+‘0‘);
for(int i=small-1;i<n-dep;i++) num[i]=num[i+1];
dep++;
}
return s;
}
};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。