# Leetcode 60 kth permutation

2020-11-13 20:03:56

## LeetCode60 The first k Permutation

### Title Description

Give set `[1,2,3,...,n]`, All of its elements have `n!` Species arrangement .

List all permutations in order of size , And mark one by one , When `n = 3` when , All arranged as follows ：

``````"123"
"132"
"213"
"231"
"312"
"321"
``````

Given `n` and `k`, Back to page `k` Permutation .

### Examples

`````` Input ：n = 3, k = 3
Output ："213"
``````
`````` Input ：n = 4, k = 9
Output ："2314"
``````
`````` Input ：n = 3, k = 1
Output ："123"
``````

### Algorithm analysis

• Enumerate each location
• Consider each bit from high to low ;
• For everyone , Enumerate the unused numbers from small to large , Determine what the current bit is

### Java Code

``````class Solution {
public String getPermutation(int n, int k) {
boolean[] st = new boolean;
int[] f = new int; // Existential factorial
f = 1;
for(int i = 1; i <= n; i++){
f[i] = f[i - 1] * i;
}

String ans = "";
for(int i = 0; i < n; i ++){
for(int j = 1; i <= n; j++){
if(!st[j]){
if(k <= f[n-i-1]){
ans = ans + "" + j;
st[j] = true;
break;
}
k -= f[n-i-1];
}
}
}

return ans;
}
}
``````