forked from walnutown/CodingInTheDeep
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathPermutationSequence.java
More file actions
64 lines (59 loc) · 1.67 KB
/
Copy pathPermutationSequence.java
File metadata and controls
64 lines (59 loc) · 1.67 KB
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
/*
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.
*/
// use nextPermutation, TLE
public class Solution {
public String getPermutation(int n, int k) {
char[] p = new char[n];
for (int i=0; i<n; i++) p[i] = (char)(i+'1');
int len=1;
for (int i=1; i<=n; i++) len*=i;
k = k%len==0 ? len:k%len; // in case k is larger than the total number of sequence
for (int i=2; i<=k; i++){
nextPermutation(p);
}
return String.valueOf(p);
}
public void nextPermutation(char[] p){
int l = p.length - 1;
while (l > 0 && p[l - 1] > p[l]) l--;
Arrays.sort(p, l, p.length);
if (l == 0) return;
int i = l;
while (p[l-1] >= p[i] && i<p.length) i++;
char tmp = p[l-1];
p[l-1] = p[i];
p[i] = tmp;
}
}
// from AnnieKim, calculate each digit one by one
public class Solution {
public String getPermutation(int n, int k) {
StringBuilder num = new StringBuilder(), res = new StringBuilder();
int len=1;
for (int i=1; i<=n; i++){
num.append(i);
len *= i;
}
k--; // notice, IMPORTANT here
while (n > 0){
len /= n;
int i = k/len;
k %= len;
res.append(num.charAt(i));
num.deleteCharAt(i);
n--;
}
return res.toString();
}
}