# 60.Permutation-Sequence

## 60. Permutation Sequence

## 题目地址

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

## 题目描述

```
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.

Note:

Given n will be between 1 and 9 inclusive.
Given k will be between 1 and n! inclusive.
Example 1:

Input: n = 3, k = 3
Output: "213"
Example 2:

Input: n = 4, k = 9
Output: "2314"
```

## 代码

### Approach #1 Factorial Number System

```java
class Solution {
  public String getPermutation(int n, int k) {
        int[] factorials = new int[n];
    List<Integer> nums = new ArrayList() {{ add(1);}};

    factorials[0] = 1;
    for (int i = 1; i < n; i++) {
      factorials[i] = factorials[i - 1] * i;
      nums.add(i + 1);
    }

    k--;

    StringBuilder sb = new StringBuilder();
    for (int i = n - 1; i > -1; i--) {
      int idx = k / factorials[i];
      k -= idx * factorials[i];

      sb.append(nums.get(idx));
      nums.remove(idx);
    }

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