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

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

Given `n` and `k`, return the `kth` permutation sequence.

Example 1:

```Input: n = 3, k = 3
Output: "213"
```

Example 2:

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

Example 3:

```Input: n = 3, k = 1
Output: "123"
```

Constraints:

• `1 <= n <= 9`
• `1 <= k <= n!`

60. Permutation Sequence
``````struct Solution;

impl Solution {
fn get_permutation(n: i32, k: i32) -> String {
let n = n as usize;
let mut k = k as usize - 1;
let mut nums: Vec<usize> = (1..=n).collect();
let mut factorial = vec![1];
let mut prev = 1;
for x in 1..n {
prev *= x;
factorial.push(prev);
}
let mut res = vec![];
for i in 0..n {
let index = k / factorial[n - 1 - i];
res.push(nums.remove(index));
k %= factorial[n - 1 - i];
}
res.into_iter().map(|x| (x as u8 + b'0') as char).collect()
}
}

#[test]
fn test() {
let n = 3;
let k = 3;
let res = "213".to_string();
assert_eq!(Solution::get_permutation(n, k), res);
let n = 4;
let k = 9;
let res = "2314".to_string();
assert_eq!(Solution::get_permutation(n, k), res);
let n = 3;
let k = 5;
let res = "312".to_string();
assert_eq!(Solution::get_permutation(n, k), res);
}
``````