题目描述
给出集合 [1,2,3,…,n]
,其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下:
"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k,返回第 k 个排列。
说明:
- 给定 n 的范围是 [1, 9]。
- 给定 k 的范围是[1, n!]。
示例 1:
输入: n = 3, k = 3
输出: "213"
示例 2:
输入: n = 4, k = 9
输出: "2314"
解题思路
类似于找下一个排列的做法,不过如果从头开始一直到第k个就太费时了,所以考虑从头开始针对每个位置找到第k个排列的确定数字,例如对于示例2中的n = 4, k = 9,第一个数一定为2,因为以1开头的排列总数为3!=6,9>6且9-6<6,所以第9个排列的首数字为1后一个数字2,即找到第7个排列为2134,同样对于第二个位置找到首数字为3,此时即找到了第9个排列为2314。注意每次找到首位置数字后,要将其后的数字从小到大重新排序才是下一个排列。
代码
class Solution {
public:
string getPermutation(int n, int k) {
string s = "";
for(int i = ; i <= n; i++)
s += to_string(i);
int idx = ;
while(k > ){
int sum = fac(n - idx - ), i = ;
while(k > sum){
k -= sum;
i++;
}
swap(s[idx], s[idx + i]);
sort(s.begin() + ++idx, s.end());
}
return s;
}
int fac(int n){
int res = ;
while(n > )
res *= n--;
return res;
}
};