My solution in cpp, fairly concise

• My thought is:

1. store the available numbers, store the n factor values
2. go through each char in the target string, fill it with expected value directly.
3. the expected value is calculated as t = number[(k-1)/(n-1)!], if k is counted down to 0, t should be end of the available numbers, then k update to k%(n-1)!
e.g. if n=3, k=2,
the first expected value is indexed at 1/2 = 0 in available numbers (1, 2, 3), t = 1. k is updated to 0
the second expected value is indexed at 1 since k=0 in available numbers: (2, 3), t = 3. k is updated to 0
the third expected value is indexed at 0 in available numbers (2), t = 0, k is still 0.

The code is:

``````string getPermutation(int n, int k) {
if (n <= 0 || k <= 0) return "";
vector<int> factor(n + 1, 1);
vector<int> array(n, 1);
string s(n, '0');

for (int i = 1; i < n; i++) {
factor[i] = factor[i - 1] * i;
array[i] = i + 1;
}

int j = n;
for (int i = 0; i < n; i++) {
int count = k ? (k-1)/factor[j-1] : j - 1;
k = k%factor[j-1];
if (count > n) break;
s[i] += array[count];
array.erase(array.begin() + count);
j--;
}

return s;
}
``````

The time complexity should be O(n^2) since erase element from array takes n. space complexity is O(n)

• My java solution with a similar idea.

``````public class Solution {
String result="";
int[] array;
public String getPermutation(int n, int k) {
array=new int[n+1];

for (int i=0;i<n;i++)
array[i]=i+1;
array[n]=0;

int perm=1;
for (int i=1;i<=n;i++)
perm*=i;

doPermutationHelper(array,perm,n,k);
return result;

}
private void doPermutationHelper(int[] a,int perm,int n,int k){
if (n==1) {
result+=String.valueOf(a[0]);
return;
}

perm/=n;
int i=(k-1)/perm;
result+=String.valueOf(a[i]);
while (i<n-1)
a[i++]=a[i];
doPermutationHelper(a,perm,n-1,(k-1)%perm+1);
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.