力扣每日一题60：排序序列

题目描述：

给出集合 [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 <= n <= 9
• 1 <= k <= n!

通过次数

134.3K

提交次数

250.8K

通过率

53.5%

思路和题解：

先构建一个[1,2,......,n]数组，此时是第1个排列，用next_permutation函数，每使用一次，就是下一个序列。该函数使用k次即可。

代码：

class Solution {
public:
    string getPermutation(int n, int k) {
        int i=0;
        string a(n,0);
        for(i=0;i<n;i++) a[i]=i+1+'0';
        int cnt=0;
        do{
            cnt++;
        }while(cnt<k&&next_permutation(a.begin(),a.end()));
        return a;
    }
};