题目描述

题目链接

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

“123”
“132”
“213”
“231”
“312”
“321”
给定 n 和 k，返回第 k 个排列。

 

样例

1
2
3
4
示例 1：

输入：n = 3, k = 3
输出："213"
1
2
3
4
示例 2：

输入：n = 4, k = 9
输出："2314"
1
2
3
4
示例 3：

输入：n = 3, k = 1
输出："123"
1
2
3
4
提示：

1 <= n <= 9
1 <= k <= n!

算法1

(枚举) $O(n^2)$

由于需要快速计算出从小到大第 k 位的排列值，那么我们可以考虑当确定了 i 位数字时，排列数目的变化；

首先，当任意一位数字都未确定时，总共排列的数目为 $n!$种

每确定一位数字， 剩余的排列数就会相应的变为 $(n - 1)!$种

那么，我们可以从小到大枚举尚未选择的最小数字，若当前第 k 个排列大于剩余的排列数 $(n - i)!$，那么说明第 k 个排列应该在以更大数字为起始的排列当中

C++ 代码

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
class Solution {
public:
    string getPermutation(int n, int k) {
        vector<bool> st(n);
        string res = "";
        for(int i = 0; i < n; i ++)
        {
            int f = 1;
            for(int j = 1; j < n - i; j ++) f *= j;
            for(int j = 0; j < n; j ++)
            {
                if( !st[j])
                {
                    if( k <= f)
                    {
                        st[j] = true;
                        res += (j + '0' + 1);
                        break;
                    }
                    k -= f;
                }
            }
        }

        return res;
    }
};