> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/math/permutation-sequence.md).

# Permutation Sequence

<https://leetcode.com/problems/permutation-sequence/description/>

> 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, forn= 3):
>
> 1. `"123"`
> 2. `"132"`
> 3. `"213"`
> 4. `"231"`
> 5. `"312"`
> 6. `"321"`
>
> Givennandk, return thekthpermutation sequence.

## Thoughts

把首位固定, 那每组会有(N-1)!个数. 我们让k/(N - 1)!就可以知道kth的第一个数是多少. 这时我们要把第一个数从nums中移出去, 更新k = k % (N - 1)!. 同理判断第二个数的index是多少. 依次类推下去.

## Code

```
class Solution {
    public String getPermutation(int n, int k) {
        int[] fac = new int[n + 1];
        fac[0] = 1;
        for (int i = 1; i <= n; i++) {
            fac[i] = fac[i - 1] * i;
        }
        List<Integer> numbers = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            numbers.add(i);
        }

        StringBuilder sb = new StringBuilder();
        k--;
        for (int i = 1; i <= n; i++) {
            int index = k / fac[n - i];
            sb.append(String.valueOf(numbers.get(index)));
            k = k % fac[n - i];
            numbers.remove(index);
        }

        return sb.toString();
    }
}
```

## Analysis

Errors:\
1\. k在运算前必须-1.\
时空复杂度为O(N).