题目内容

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

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

1、”123”
2、”132”
3、”213”
4、”231”
5、”312”
6、”321”
给定 n 和 k，返回第 k 个排列。

示例

示例 1：

输入：n = 3, k = 3
输出：”213”
示例 2：

输入：n = 4, k = 9
输出：”2314”
示例 3：

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

提示

1、1 <= n <= 9
2、1 <= k <= n!

题解

本题求解的是序列的全排列中第k个排列是什么，由于C++中有对应的函数可以求解，因此使用C++语言求解的话，使用next_permutation()函数就可以求解出来。这个函数会把当前排列的下一个字典序排列求出来，因此循环k-1次之后就可以求出第k个的排列。

但是，本题主要考察的并不是上述函数，而是求解的思路，因此这里来说说如何按照正常的算法思路求解。

具体做法是按位求解，即：

1、从高位到低位依次考虑每一位；
2、对于每一位，从小到大依次枚举未使用过的数，确定当前位是几；

比如：n=5，k=10

首先思考首位：

1+（2、3、4、5的全排列），有24种排列方式

2+（1、3、4、5的全排列），有24种排列方式

3+（1、2、4、5的全排列），有24种排列方式

4+（1、2、3、5的全排列），有24种排列方式

5+（1、2、3、4的全排列），有24种排列方式

第10个的排列一定在首位为1的排列方式中，因此确定首位一定是1。

然后继续判断第二位。

12+（3、4、5的全排列），有6种排列方式

13+（2、4、5的全排列），有6种排列方式

14+（2、3、5的全排列），有6种排列方式

15+（2、3、4的全排列），有6种排列方式

由于每组6种排列，因此10-6=4，全局第10个排列在第二组，因此前两位的序列确定为13。

然后判断第三位

132+（4、5的全排列），有2种排列方式

134+（2、5的全排列），有2种排列方式

135+（2、4的全排列），有2种排列方式

由于每组2种排列，因此4-2=2，全局第10个排列在第二组，因此前三位序列确定为134。

然后判断第4位

1342+（5的全排列），有1种排列方式

1345+（2的全排列），有1种排列方式

由于每组1种排列，因此2-1*2=0，因此前四位序列确定为1345。

由于前4位全部确定，最后一位一定确定，最终答案是13452.

代码

// class Solution {
// public:
//     string getPermutation(int n, int k) {
//         //语法做法。循环k次就是所求
//         string res;
//         for(int i = 1;i <= n; i++) res+=to_string(i);
//         for(int i = 0; i < k - 1; i++){
//             next_permutation(res.begin(),res.end());
//         }
//         return res;
//     }
// };


class Solution {
public:
    string getPermutation(int n, int k) {
        string res;
        vector<bool> st(10); //记录哪些数被用过
        for (int i = 0; i < n; i ++ ) {
            //每填一个数后面有(n - i - 1)!个数
            int fact = 1;
            for (int j = 1; j <= n - i - 1; j ++ ) fact *= j;

            for (int j = 1; j <= n; j ++ ) {
                if (!st[j]) {
                    if (fact < k) k -= fact; //判断第k个数是否应填j
                    else {
                        res += to_string(j);
                        st[j] = true;
                        break;
                    }
                }
            }
        }

        return res;
    }
};