60. 排列序列
给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123""132""213""231""312""321"
给定 n 和 k，返回第 k 个排列。
示例 1：
输入：n = 3, k = 3
输出："213"
示例 2：
输入：n = 4, k = 9
输出："2314"
示例 3：
输入：n = 3, k = 1
输出："123"
提示：
1 <= n <= 91 <= k <= n!
方法一：next_permutation
很明显，本题如果直接回溯出结果取第k个是肯定会超时的。
但是可以用C++的next_permutation水过
class Solution {
public:
string getPermutation(int n, int k) {
vector<int> initial_state(n);
iota(initial_state.begin(), initial_state.end(), 1);
while(--k) {
next_permutation(initial_state.begin(), initial_state.end());
}
string res;
for (auto& c : initial_state) res += c +'0';
return res;
}
};
面试官如果要让你回去吧的时候，你可以说我会自己写next_permutation应该是问题不大的。
问题转化为31. 下一个排列，也就是自己造出next_permutation这个轮子
找到下一个全排列可以用以下步骤
123
- 从尾到头找到第一个非降序的位置。
while(k > 0 && nums[k] <= nums[k - 1]) k--
如果k == 0，说明该序列从头到尾都是保持一个非降序的形态。比如1,2,3。此时我们直接reverse即可。
-
从k开始，找到右侧第一个小于等于当前数字。
-
对2个数字进行交换。并且部分反转。
举个例子 1 3 2
k从2开始，遍历到3，变成了1.
t从k开始，往右边找，找不到比他小的，出界到了3.
此时t是3，k是1. 交换nums[k - 1]和nums[t - 1]
变成231，从k开始反转到最后，变成213.
其实是非常非常难想到的一个概念，至少对于我来说是纯粹靠记忆了。找规律的话需要花费很多时间。
class Solution {
public:
string getPermutation(int n, int k) {
vector<int> initial_state(n);
iota(initial_state.begin(), initial_state.end(), 1);
auto myNextPermutation = [&] (vector<int>& nums) {
int k = nums.size() - 1;
while (k > 0 && nums[k] <= nums[k - 1]) k--;
if (k <= 0) {
reverse(nums.begin(), nums.end());
} else {
int t = k;
//找到右侧第一个小于等于当前数的
while (t < nums.size() && nums[t] > nums[k - 1]) t++;
swap(nums[k - 1], nums[t - 1]);
reverse(nums.begin() + k, nums.end());
}
};
while(--k) {
myNextPermutation(initial_state);
}
string res;
for (auto& c : initial_state) res += c +'0';
return res;
}
};
方法二: 数学
康托展开运算
$X = a_n(n-1)! + a_{n-1}(n-2)! + ··· + a_1·0!$
其中$a_i$为整数，并且$0\leq a_i<i, 1 \leq i \leq n$
$a_i$表示原数的第i位在当前未出现的元素中是排在第几个
康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。
举个栗子
当n = 4，我们有1,2,3,4的全排列集合。
根据康拓展开，我们可以得到这个性质：
以1,2,3,4为开头的全排列的数量各为(n - 1)!，也就是6种。总共是24种。
因此，假设我们想要第10个数，其实就是2开头的数的第4个。
如此进行递归，2开头的数字后面可以接1,3,4其中每种都有2个排列。总共是6种。
我们找到3开头的第二种就是我们的答案。
一个简单的递归关系：
对n个数字来说，每个组有着(n - 1) !个全排列。
因此n - 1个数字，每个组会有(n - 2)!个全列
所以对特定数字来说。
k/(n - 1)! 可以得到当前数字的下标。
剩下的n - 1个数字则用k % (n - 1) 来进行讨论。
直到n个0，我们得到的就是第k个。
class Solution {
public:
string getPermutation(int n, int k) {
string res;
string tmp = "";
for (int i = 1; i <= n; i++) {
tmp += to_string(i);
}
vector<int> fac(n);
fac[0] = 1;
for(int i = 1; i < n; i++) fac[i] = fac[i - 1] * i; // 提前计算好需要的阶乘结论
--k; // 坑点 死在这里的人好多
for (int i = n; i > 0; i--) {
int idx = k / fac[i - 1];
k %= fac[i - 1];
res += tmp[idx];
tmp.erase(tmp.begin() + idx);
}
return res;
}
};
