forked from hongtaocai/code_interview
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathPermutationSequence.cpp
More file actions
39 lines (39 loc) · 993 Bytes
/
PermutationSequence.cpp
File metadata and controls
39 lines (39 loc) · 993 Bytes
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
class Solution {
public:
string getPermutation(int n, int k) {
if(n==0) {
return "";
}
string perm = "";
int factorial = 1;
k--;
for(int i=1;i<n;++i) {
factorial*= i;
}
vector<int> remainingNumbers(n);
for(int i=0;i<n;++i) {
remainingNumbers[i] = i+1;
}
for(int i=0;i<n;i++) {
int index = k/factorial;
k = k%factorial;
if(factorial!=1) {
factorial /= (n-1-i);
}
int j=0;
while(true) {
if(remainingNumbers[j]<0) {
j++;
} else if(index==0) {
perm += char('0' + remainingNumbers[j]);
remainingNumbers[j] = -1;
break;
} else {
--index;
j++;
}
}
}
return perm;
}
};