Given an array, find the next permutation of the sequence. If the sequence is already the largest permutation, output the smallest sorted order.
The key is to have a clear approach.
Find the first element worth swapping – it should be as close to the least significant position as possible, and there must be a larger element after it. Then find the smallest element after it that is larger and swap them.
Finally, sort all elements after the swapped position in ascending order.
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
| int cmp(int a,int b) {
return a < b;
}
class Solution {
public:
void nextPermutation(vector<int> &num) {
bool IsSwap = false;
for(int i = num.size()-1;i >= 0;i--) {
int index = -1;
int max = 0xffff;
for(int j = i+1;j < num.size();j++) {
if(num[j] > num[i] && num[j] < max) {
index = j;
max = num[j];
IsSwap = true;
}
}
if(IsSwap) {
int tmp = num[index];
num[index] = num[i];
num[i] = tmp;
sort(num.begin()+i+1,num.end(),cmp);
break;
}
}
if(IsSwap == false) {
sort(num.begin(),num.end(),cmp);
}
}
};
|