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!

Rust Solution

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);
}

Having problems with this solution? Click here to submit an issue on github.