题目描述
Given
n
andk
, return thekth
permutation sequence.
The set
[1, 2, 3, ..., n]
contains a total ofn!
unique permutations.
By listing and labeling all of the permutations in order, we get the following sequence for n = 3
:
"123"
"132"
"213"
"231"
"312"
"321"
例子
例子 1
Input:
n = 3, k = 3
Output:"213"
例子 2
Input:
n = 4, k = 9
Output:"2314"
例子 3
Input:
n = 3, k = 1
Output:"123"
Constraints
1 <= n <= 9
1 <= k <= n!
解题思路
在题目中给出的例子中可以发现,对于 n = 3
的所有情况,可以按照首元素 1
和 2
和 3
均等的分为 3 组,每一组中有 (n - 1)!
个。以此我们可以发现一个规律,对于 n
个数字的排列情况来说,它的所有排列可以分为 n
组,每组中有 (n - 1)!
个子排列。我们要求第 k
个的话,第一步可以首先用 k / (n - 1)!
就知道我们要求的排列落在哪一个组中,在对于该组中我们递归的用 k = k % (n - 1)!, n = n - 1
进行重复计算即可,终止情况是 n = 1
此时只有一种排列即该数字本身。具体操作过程中,由于每次循环我们都会用掉一个元素,所以需要在该序列中,把那个数字去掉。
代码如下:
#include <string>
#include <vector>
class Solution {
public:
std::string getPermutation(int n, int k) {
std::vector<int> nums;
std::vector<int> factorial(10, 1);
for (int i = 1; i <= 9; i++) {
nums.push_back(i);
factorial[i] = factorial[i - 1] * i;
}
std::string perm = "";
k--;
while (n > 0) {
int select = k / factorial[n - 1];
k %= factorial[n - 1];
perm += '0' + nums[select];
for (int i = select; i < nums.size() - 1; ++i) {
nums[i] = nums[i + 1];
}
n--;
}
return perm;
}
};
- 时间复杂度: O(n)
- 空间复杂度: O(1)
GitHub 代码同步地址: 60.PermutationSequence.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions