# 0060. 第 k 个排列
### 题目地址(60. 第 k 个排列)
### 题目描述
```
给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。
说明：
给定 n 的范围是 [1, 9]。
给定 k 的范围是[1, n!]。
示例 1:
输入: n = 3, k = 3
输出: "213"
示例 2:
输入: n = 4, k = 9
输出: "2314"
```
### 前置知识
* 数学
* 回溯
* factorial
### 公司
* 阿里
* 百度
* 字节
* Twitter
### 思路
LeetCode 上关于排列的题目截止目前（2020-01-06）主要有三种类型：
* 生成全排列 [46. 全排列](/leetcode-solution/medium/46.permutations.md) [47. 全排列 II](/leetcode-solution/medium/47.permutations-ii.md)
* 生成下一个排列 [31. 下一个排列](/leetcode-solution/medium/31.next-permutation.md)
* 生成第 k 个排列（我们的题目就是这种）
我们不可能求出所有的排列，然后找到第 k 个之后返回。因为排列的组合是 N！，要比 2^n 还要高很多，非常有可能超时。我们必须使用一些巧妙的方法。
我们以题目中的 n= 3 k = 3 为例：
* "123"
* "132"
* "213"
* "231"
* "312"
* "321"
可以看出 1xx，2xx 和 3xx 都有两个。如果你了解阶乘的话，应该知道这实际上是 2！个。
以上面的例子为例，假设我们想要找的是第 3 个。那么我们可以**直接跳到** 2 开头，因为我们知道以 1 开头的排列有 2 个，可以直接跳过，问题缩小了。
于是我们将 2 加入到结果集的第一位，不断重复上述的逻辑，直到结果集的长度为 n 即可。
### 关键点解析
* 找规律
* 排列组合
### 代码
* 语言支持: Python3
```python
import math
class Solution:
def getPermutation(self, n: int, k: int) -> str:
res = ""
candidates = [str(i) for i in range(1, n + 1)]
while n != 0:
facto = math.factorial(n - 1)
# i 表示前面被我们排除的组数，也就是k所在的组的下标
# k // facto 是不行的， 比如在 k % facto == 0的情况下就会有问题
i = math.ceil(k / facto) - 1
# 我们把candidates[i]加入到结果集，然后将其弹出candidates（不能重复使用元素）
res += candidates[i]
candidates.pop(i)
# k 缩小了 facto * i
k -= facto * i
# 每次迭代我们实际上就处理了一个元素，n 减去 1，当n == 0 说明全部处理完成，我们退出循环
n -= 1
return res
```
**复杂度分析**
* 时间复杂度：$O(N^2)$
* 空间复杂度：$O(N)$
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/60.permutation-sequence.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.