### 题目

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 (ie, 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.

### 真的转k次，$O(kn)$

12345
12354
12435
12453
12534 <-- k=5
12543


#### 代码

public class Solution {
public String getPermutation(int n, int k) {
char[] array = new char[n];
for (int i = 0; i < n; i++) {
array[i] = (char)('0'+i+1);
}
for (int i = 1; i < k; i++) {
rotate(array);
}
return new String(array);
}
public void rotate(char[] array) {
char c = Character.MIN_VALUE;
int target = -1;
for (int i = array.length-1; i >= 0; i--) {
if (array[i] < c) {
target = i;
break;
} else {
c = array[i];
}
}
if (target != -1) {
for (int i = array.length-1; i > target; i--) {
if (array[i] > array[target]) {
char temp = array[target];
array[target] = array[i];
array[i] = temp;
break;
}
}
}
for (int start = target+1, end = array.length-1; start < end; start++,end--) {
char temp = array[start];
array[start] = array[end];
array[end] = temp;
}
}
}


### 数学公式计算出结果

1  12345
2  12354
3  12435
4  12453
5  12534
6  12543
7  13245 #第7次，第二个数变3
8  13254
9  13425
10 13452
11 13524
12 13542
13 14235 #第13次，第二个数变4
14 14253
15 14325
16 14352
17 14523
18 14532
19 15234 #第19次，第二个数变5
20 15243
21 15324
22 15342
23 15423
24 15432
25 21345 # 第25次，2开头，第二个数变回1
26 21354
27 21435
28 21453
29 21534
30 21543
31 23145 #第31次，第二个数变3
32 23415
33 23451
34 23514


3的阶乘3! = 3*2*1 = 6。所以高位千位，每6次加1.

#### 代码

public class Solution {
public String getPermutation(int n, int k) {
List<Character> nums = new ArrayList<>();
for (int i = 1; i <= n; i++) {
}
char[] res = new char[n];
int period; // 循环周期，5位数的话，首位数的循环周期就是[5-0-1]!，就是4的阶乘，等于24
k--; // 调整序数，题目是从1开始
for (int index = 0; index < n; index++) {
period = 1;
for (int i = n - index - 1; i > 0; i--) {
period *= i;
}
res[index] = nums.remove(k/period);
k = k % period;
}
return new String(res);
}
}