# 60. Permutation Sequence 排列序列

@TOC

## # 题目描述

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:

``````"123"
"132"
"213"
"231"
"312"
"321"
``````

Given n and k, return the kth permutation sequence.

Note:

• Given n will be between 1 and 9 inclusive.
• Given k will be between 1 and n! inclusive.

Example 1:

``````Input: n = 3, k = 3
Output: "213"
``````

Example 2:

``````Input: n = 4, k = 9
Output: "2314"
``````

## # 解题方法

``````1234
1243
1324
1342
1423
1432
2134
2143
2314  <= k = 9
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321
``````

a1 = k / (n - 1)! k1 = k

a2 = k1 / (n - 2)! k2 = k1 % (n - 2)! ...

an-1 = kn-2 / 1! kn-1 = kn-2 % 1!

an = kn-1 / 0! kn = kn-1 % 0!

``````class Solution(object):
def getPermutation(self, n, k):
"""
:type n: int
:type k: int
:rtype: str
"""
ans = ''
fact = [1] * n
num = [str(i) for i in range(1, 10)]
for i in range(1, n):
fact[i] = fact[i - 1] * i
k -= 1
for i in range(n, 0, -1):
first = k // fact[i - 1]
k %= fact[i - 1]
ans += num[first]
num.pop(first)
return ans
``````

C++代码如下：

``````class Solution {
public:
string getPermutation(int n, int k) {
string res;
string num = "123456789";
vector<int> f(n, 1);
for (int i = 1; i < n; i++) f[i] = f[i - 1] * i;
--k;
for (int i = n; i >= 1; i--) {
int j = k / f[i - 1];
k %= f[i - 1];
res.push_back(num[j]);
num.erase(j, 1);
}
return res;
}
};
``````

## # 日期

2018 年 6 月 11 日 —— 今天学科三在路上跑的飞快～ 2018 年 12 月 22 日 —— 今天冬至