/
_60.java
executable file
·70 lines (63 loc) · 1.58 KB
/
_60.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
package com.hit.basmath.learn.others;
import java.util.ArrayList;
import java.util.List;
/**
* 60. Permutation Sequence
* <p>
* The set [1,2,3,...,n] contains a total of n! unique permutations.
* <p>
* By listing and labeling all of the permutations in order, we get the following sequence for n = 3:
* <p>
* "123"
* "132"
* "213"
* "231"
* "312"
* "321"
* <p>
* Given n and k, return the kth permutation sequence.
* <p>
* Note:
* <p>
* Given n will be between 1 and 9 inclusive.
* Given k will be between 1 and n! inclusive.
* <p>
* Example 1:
* <p>
* Input: n = 3, k = 3
* Output: "213"
* <p>
* Example 2:
* <p>
* Input: n = 4, k = 9
* Output: "2314"
*/
public class _60 {
public String getPermutation(int n, int k) {
int pos = 0;
List<Integer> numbers = new ArrayList<>();
int[] factorial = new int[n + 1];
StringBuilder sb = new StringBuilder();
// create an array of factorial lookup
int sum = 1;
factorial[0] = 1;
for (int i = 1; i <= n; i++) {
sum *= i;
factorial[i] = sum;
}
// factorial[] = {1, 1, 2, 6, 24, ... n!}
// create a list of numbers to get indices
for (int i = 1; i <= n; i++) {
numbers.add(i);
}
// numbers = {1, 2, 3, 4}
k--;
for (int i = 1; i <= n; i++) {
int index = k / factorial[n - i];
sb.append(String.valueOf(numbers.get(index)));
numbers.remove(index);
k -= index * factorial[n - i];
}
return String.valueOf(sb);
}
}