In this Leetcode Permutation Sequence Problem Solution 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 for n = 3:
"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.
Problem solution in Python.
class Solution(object):
def getPermutation(self, n, k):
r = ''; fac = [1]*(n+1); s = []
for i in xrange(1, n+1):
fac[i] = i*fac[i-1]
s.append(i)
for i in xrange(n, 0, -1):
ind = (k-1)/fac[i-1]
r += str(s[ind])
del s[ind]
k %= fac[i-1]
return rProblem solution in Java.
class Solution {
String result;
int K = 0;
public String getPermutation(int n, int k)
{
int[] counts = new int[10];
for(int i = 1; i <=n; i++)
{
counts[i] = 1;
}
K = k;
dfs(counts, n, new StringBuilder());
return result;
}
void dfs(int[] counts, int n, StringBuilder sb)
{
if(sb.length() == n)
{
K = K-1;
if(K == 0)
{
result = sb.toString();
return;
}
}
for(int i = 1; i < counts.length; i++)
{
if(counts[i] > 0)
{
sb.append(String.valueOf(i));
counts[i]--;
dfs(counts, n, sb);
sb.deleteCharAt(sb.length()-1);
counts[i]++;
}
}
}
}Problem solution in C++.
void nextPermutation(string &s)
{
int n=s.size();
int idx1=n-1;
while(idx1>0&&((s[idx1]-'0')<(s[idx1-1]-'0')))
{
idx1--;
}
idx1--;
int j=n-1;
while((s[idx1]-'0')>(s[j]-'0'))
{
j--;
}
swap(s[idx1],s[j]);
j=n-1;
idx1++;
while(idx1<=j)
{
swap(s[idx1],s[j]);
j--;
idx1++;
}
}
string getPermutation(int n, int k) {
string s="";
for(char z='1';z<=n+'0';z++)
{
s+=z;
}
for(int z=1;z<k;z++)
{
nextPermutation(s);
}
return s;
}Problem solution in C.
char * getPermutation(int n, int k){
int anscnt=0;
char *ans=malloc(sizeof(char)*(n+1));
ans[n]='\0';// for C you need to care about the end of the string , or you will get RE
if(n==1){
ans[0]='1';
return ans;
}
int picked[n+1];
memset(picked,0,sizeof(int)*(n+1));
int factorial=1;
for(int i=2;i<=n;i++){
//calculate the factorial or all number first, so we only need O(N) time on each factorial
factorial*=i;
}
for(int i=n-1;i>=1;i--){
factorial/=(i+1);// for each i , the factorial of it
int max,loccnt=0;
//max : subproblem answer's first number
if(k%factorial==0){
max=k/factorial-1;
}
else{
max=k/factorial;
}
k-=(max*factorial);// the index for the next subproblem
for(int j=1;j<=n;j++){
//choose the first number of the subproblem
if(picked[j]==0){
if(loccnt==max){
ans[anscnt++]=j+'0';
picked[j]=1;
break;
}
loccnt++;
}
}
if(k<=1){
// the rest are the sorted array , so we end the problem
for(int j=1;j<=n;j++){
if(picked[j]==0){
ans[anscnt++]=j+'0';
}
}
break;
}
}
return ans;
}
0 Comments