mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
69 lines
2.3 KiB
Markdown
69 lines
2.3 KiB
Markdown
# [60. Permutation Sequence](https://leetcode.com/problems/permutation-sequence/)
|
||
# 思路
|
||
给定整数n，返回数组[1,2,...,n]的第k个permutation。
|
||
## 思路一
|
||
STL中有函数next_permutation可以返回一个数组的下一个permutation，所以最简单的思路就是执行这个函数k-1次即可得到第k个permutation。
|
||
next_permutation的时间复杂度是O(n), 所以总的复杂度就是O(kn), 空间复杂度O(1)
|
||
|
||
## 思路二
|
||
让我们仔细看看n=3的例子：
|
||
```
|
||
1. "123"
|
||
2. "132"
|
||
3. "213"
|
||
4. "231"
|
||
5. "312"
|
||
6. "321"
|
||
```
|
||
可以看到第一个元素分别为1、1、2、2、3、3，所以我们可以根据k的值直接得到结果的第一个元素，例如若k=3，那么结果第一元素就是2。
|
||
一般化一点，所有排列中第一个元素为1~n，每个都出现了(n-1)!次，可根据k直接得到结果的第一个元素值，可以根据同样的思路得到第2、3...直至整个结果。
|
||
时间复杂度O(n^2), 空间复杂度O(n), 因为k可以比n大很多，所以比思路一快很多。
|
||
|
||
# C++
|
||
## 思路一
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
string getPermutation(int n, int k) {
|
||
string res = "";
|
||
for(int i = 0; i < n; i++) res += (i + '1');
|
||
while(--k){
|
||
next_permutation(res.begin(), res.end());
|
||
}
|
||
return res;
|
||
}
|
||
};
|
||
```
|
||
## 思路二
|
||
``` C++
|
||
class Solution {
|
||
private:
|
||
char get_k_th_not_0(vector<int> &nums, int k){ // 获得第k个还没用过的数字对应的字符
|
||
k += 1; // 传进来的k是从0开始的
|
||
int i = -1;
|
||
while(k--){
|
||
i++;
|
||
while(i < nums.size() && nums[i] == 0) i++;
|
||
}
|
||
nums[i] = 0; // 数字i(对应字符i+"1")已经用过了，更新nums
|
||
return i + '1';
|
||
}
|
||
public:
|
||
string getPermutation(int n, int k) {
|
||
string res = "";
|
||
vector<int>nums(n, 1); // 若nums[i]=1说明数字i(对应字符i+"1")还没用过
|
||
int product = 1;
|
||
k -= 1; // 从0开始
|
||
for(int i = 1; i <= n; i++) product *= i; // product = n!
|
||
|
||
for(int i = n; i >= 1; i--){
|
||
product /= i; // 此时k代表每个第一个元素出现的次数
|
||
int tmp = k / product;
|
||
k %= product; // 更新k
|
||
res += get_k_th_not_0(nums, tmp);
|
||
}
|
||
return res;
|
||
}
|
||
};
|
||
```
|