LeetCode60-第k个排列
LeetCode60-第k个排列
给出集合 ,其所有元素共有 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"
一、思路
(一)字典序
我们知道,如何求解下一个字典序:
(1)从右往左找出第一个:顺序对
(2)从的位置开始,往右找到第一个大于的数:
(3)交换与的位置
(4)将之后的数组进行翻转:
原来是:
翻转后:
(5)组合起来即得到下一个排序
这个方法显然是不适用于这道题,我们知道k最大为n!,此时这个算法的时间复杂度将会超出你的想象
(二)算数技巧
这道题本质上是一个算数的问题。
我们知道以 开头的序列有:(n-1)! 个
并且以开头的序列必然会大于以 开头的序列
所以我们知道了:
如果属于 ,那么它的排列的第一个数字一定是:1
如果属于 ,那么它的排列的第一个数字一定是:2
…
因此,我们通过这样的方法,来缩小排列的范围
在确定了第一个范围之后,第二个范围也能用同样的方法确定下来,一直到第n个数确定下来
从上面的描述可以知道,这是一个递归求解的方案。
C++代码
class Solution {
public:
string s;
string getPermutation(int n, int k) {
string sum = "123456789";
string nums = sum.substr(0, n);
recursion(k, n, nums);
return s;
}
void recursion(int k, int n, string nums) {
if (n == 0)
return;
int fact = factorial(n - 1);
int m = (k - 1) / fact;
n--;
s.push_back(nums[m]);
nums.erase(m, 1);
k -= m * fact;
recursion(k, n, nums);
}
int factorial(int n) {
int s = 1;
for (int i = 1; i <= n; i++)
s *= i;
return s;
}
};
执行效率: