LeetCode 0060 - Permutation Sequence
# Hints
- 思维
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Hard |
The set [1, 2, 3, ..., n]
contains a total of unique permutations.
By listing and labeling all of the permutations in order, we get the following sequence for :
"123"
"132"
"213"
"231"
"312"
"321"
Given and , return the permutation sequence.
Note:
Given will be between and inclusive.
Given will be between and inclusive.
Example 1:
Input: n = 3, k = 3
Output: "213"
Example 2:
Input: n = 4, k = 9
Output: "2314"
# 题意
给定两个正整数 和 ,求 到 的所有排列中字典序第 大的排列。
# 题解
由于 很小,所以我们可以迭代运行 次 next_permutation
直接得到答案,但这无法应对 较大的情况。
我们可以尝试发现 的排列的规律。为便于描述,我们用 表示序列 的字典序第 大的排列,则 即为所求。
不妨先尝试找到 的第一个数 。显然 ,此时问题的规模已经被削减至 。
进一步可以发现,在第一个数为 的 个不同的排列中、字典序第 大的排列,即为上级问题的答案。也就是说,问题可以被转化为求解 。
因此我们只需迭代 次,在第 次时,将我们找到的第 个数从序列中删除,并令 即可。
这可能有些晦涩,我们以 为例详细解释整个计算过程:
01: 1234 02: 1243 03: 1324 04: 1342 05: 1423 06: 1432
07: 2134 08: 2143 09: 2314 10: 2341 11: 2413 12: 2431
13: 3124 14: 3142 15: 3214 16: 3241 [17: 3412] 18: 3421
19: 4123 20: 4132 21: 4213 22: 4231 23: 4312 24: 4321
第 次迭代,答案的第 个数为序列 的第 个数,即 。令 。
01: 124 02: 142
03: 214 04: 241
[05: 412] 06: 421
第 次迭代,答案的第 个数为序列 的第 个数,即 。令 。
[01: 12] 02: 21
第 次迭代,答案的第 个数为序列 的第 个数,即 。
第 次迭代,答案的第 个数为序列中最后剩下的 。最后得到答案为 。
算法共需迭代 次,每次需要从数组中删除元素,因此总的时间复杂度为 。
# AC代码
class Solution {
public:
string getPermutation(int n, int k) {
// 初始化
vector<int> vec;
for (int i = 1; i <= n; i ++) {
vec.push_back(i);
}
// 预处理
int factorial[9 + 1];
factorial[0] = 1;
for (int i = 1; i <= n; i ++) {
factorial[i] = factorial[i - 1] * i;
}
// 求解
string res;
k --;
for (int i = 1; i <= n; i ++) {
// 更新答案
int idx = k / factorial[n - i];
res += (vec[idx] + '0');
// 递进
k = k % factorial[n - i];
vec.erase(vec.begin() + idx);
}
// 返回
return res;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01