1
2

输入：n = 3, k = 3
输出："213"

1
2

输入：n = 4, k = 9
输出："2314"

1
2

输入：n = 3, k = 1
输出："123"

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

struct Solution;

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 递归
    /// 1. k = c1 * (n-1)! + k'
    /// 2. k' = c2 * (n-2)!
    ///    ..
    ///    结果为 c1c2..cn
    pub fn get_permutation(n: i32, k: i32) -> String {
        let factor = (1..n).fold(vec![1], |mut acc, i| {
            acc.push(acc.last().unwrap() * i);
            acc
        });
        let mut nums = String::from("123456789").as_bytes()[..(n as usize)].to_vec();
        let mut res = vec![];
        let mut k = k - 1;
        let mut n = n;
        while k > 0 {
            let c = (k / factor[(n - 1) as usize]) as usize;
            res.push(nums.remove(c as usize));
            k %= factor[(n - 1) as usize];
            n -= 1;
        }

        String::from_utf8([res, nums].concat()).unwrap_or(String::new())
    }
}
// @lc code=end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
public:
    /*
    * ## 解题思路
    * * 数学推导
    * 1. n个字符的全排列总数为n!;
    * 2. 以任意一个字符为首字符的排列个数均(n-1)!；
    * 3. 因此，k = c1 * (n-1)! + x, 其中，c1为首字符；
    *    则第一个字符 c1 = [k / (n-1)!]， []为下取底；
    *    f(n, k) = c1 + f(n-1, k-1)
    * 4. 解题时，可以用一个字母表"123456789"来记录待取的字符；
    * 5. 将1k转换为0(k-1), 可以和上面的字母表统一，且能很好的计算
    */
    string getPermutation(int n, int k) {
        string letters = string("123456789").substr(0, n);
        string result = "";
        --k;  //将1k转化为0(k-1)
        while (k>0) {
            int i = k / getFactor(n-1);
            result.push_back(letters[i]);
            letters.erase(letters.begin()+i);
            k %= getFactor(n-1);
            n--;
        }

        return result+letters;
    }

    int getFactor(int n) {
        if (n==0) {
            return 1;
        }
        return n*getFactor(n-1);
    }
};