## [Leetcode]60. Permutation Sequence(C++)

### 题目描述

Given `n` and `k`, return the `kth` permutation sequence.

The set `[1, 2, 3, ..., n]` contains a total of `n!` unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for `n = 3`:

1. `"123"`
2. `"132"`
3. `"213"`
4. `"231"`
5. `"312"`
6. `"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!`

### 解题思路

``````#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

Built with Hugo
Theme Stack designed by Jimmy