# 60. Permutation Sequence

{% embed url="https://leetcode.com/problems/permutation-sequence/" %}

`permutation 這類的題目主要有三種`

1. `全排列 permutation`

[`https://leetcode.com/problems/permutations/`](https://leetcode.com/problems/permutations/)

[`https://leetcode.com/problems/permutations-ii/`](https://leetcode.com/problems/permutations-ii/)

`2.  kth permutation`

[`https://leetcode.com/problems/permutation-sequence/`](https://leetcode.com/problems/permutation-sequence/)

3\.  next `permutation`

[`https://leetcode.com/problems/next-permutation/`](https://leetcode.com/problems/next-permutation/)



## `kth permutation`

[http://bangbingsyb.blogspot.com/2014/11/leetcode-permutation-sequence.html](http://bangbingsyb.blogspot.com/2014/11/leetcode-permutation-sequence.html)

1. `"123"`
2. `"132"`
3. `"213"`
4. `"231"`
5. `"312"  => 5th`
6. `"321"`

`1 =>  後兩位的排列數, 即 2! = 2*1  , 即`f(n-1) 代表後面階層會經過的序列

`123`

`132`

`2 =>`&#x20;

`213`

`231`

`3 =>`&#x20;

`312`

`321`

nums = \[1, 2, 3]; // 儲存了要排列的數字

所以要得到第一位是什麼數字, &#x20;

k--; // 化為起始 0 開始的序列 // k = 4

k = k / f(n-1) // 這樣就會得到第一位的 index

k = 4/2 = 2, index 2 =  nums\[2] = 3

k = k % f(n-1); // 下輪要繼續跑的數字, 即  k 減掉 我們剛剛pass過的序列



O(n^2), nums.remove(), 需要O(n)

but Given _n_ will be between 1 and 9 inclusive.

so time complexity is small

space complexity: O(n)

```java
class Solution {
    public String getPermutation(int n, int k) {
        StringBuilder sb = new StringBuilder();
        int[] f = new int[n];
        List<Integer> nums = new ArrayList<>();
        f[0] = 1;
        
        
        for (int i = 1 ; i < n ; i++) {
            f[i] = i*f[i-1];
            nums.add(i);
        }
        nums.add(n);
        k--;
        
        for (int i = n; i > 0; i--) {
            int idx = k/f[i-1];  
            k = k % f[i-1];
            sb.append(nums.get(idx));
            nums.remove(idx);
        }
        return sb.toString();
    }
}
```
