forked from hongtaocai/code_interview
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathNextPermutation.cpp
More file actions
40 lines (38 loc) · 1.01 KB
/
NextPermutation.cpp
File metadata and controls
40 lines (38 loc) · 1.01 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
class Solution {
public:
void nextPermutation(vector<int> &num) {
if(num.size()<=1) {
return;
}
int firstDescending = 0;
for(int i=num.size()-1;i>0;i--) {
if(num[i]>num[i-1]) {
int val = num[i-1];
int j=i;
while(j<num.size()) {
if(num[j] > val) {
j++;
} else {
break;
}
}
swap(num,j-1,i-1);
reverseV(num, i, num.size()-1);
return;
}
}
reverseV(num, 0, num.size()-1);
}
void reverseV(vector<int>& num, int start, int end) {
while(start<end) {
swap(num, start, end);
start++;
end--;
}
}
void swap(vector<int>& num, int indexa, int indexb) {
int temp = num[indexa];
num[indexa] = num[indexb];
num[indexb] = temp;
}
};