File tree Expand file tree Collapse file tree 1 file changed +13
-27
lines changed Expand file tree Collapse file tree 1 file changed +13
-27
lines changed Original file line number Diff line number Diff line change 1
1
class Solution {
2
2
public:
3
- void nextPermutation (vector<int >& num) {
4
- // Start typing your C/C++ solution below
5
- // DO NOT write int main() function
6
-
7
- int n = num.size ();
8
- if (n <= 1 ) return ;
9
-
10
- bool found = false ;
11
- int i, p, maxval = INT_MIN;
12
- for (i = n - 1 ; i >= 1 ; i--) {
13
- if (maxval < num[i]) {
14
- maxval = num[i];
15
- }
16
- if (num[i-1 ] < maxval) {
17
- int delta = INT_MAX;
18
- for (int j = i; j < n; j++) {
19
- if (num[j] > num[i-1 ] && num[j] - num[i-1 ] < delta)
20
- p = j;
21
- }
22
- found = true ;
23
- break ;
24
- }
3
+ void nextPermutation (vector<int > &num) {
4
+ int i = num.size () - 1 ;
5
+ while (i >= 1 && num[i-1 ] >= num[i]) {
6
+ i--;
25
7
}
26
- if (!found ) {
8
+ if (i == 0 ) {
27
9
reverse (num.begin (), num.end ());
10
+ return ;
28
11
}
29
- else {
30
- swap (num[p], num[i-1 ]);
31
- sort (num.begin () + i, num.end ());
12
+ for (int j = num.size () - 1 ; j >= i; j--) {
13
+ if (num[j] > num[i-1 ]) {
14
+ swap (num[j], num[i-1 ]);
15
+ break ;
16
+ }
32
17
}
18
+ reverse (num.begin () + i, num.end ());
33
19
}
34
- };
20
+ };
You can’t perform that action at this time.
0 commit comments