8000 3 · zwxalgorithm/leetcode-1@1ed8730 · GitHub
[go: up one dir, main page]

Skip to content

Commit 1ed8730

Browse files
committed
3
1 parent 316c365 commit 1ed8730

File tree

1 file changed

+13
-27
lines changed

1 file changed

+13
-27
lines changed

NextPermutation/NextPermutation.cpp

Lines changed: 13 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -1,34 +1,20 @@
11
class Solution {
22
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--;
257
}
26-
if (!found) {
8+
if (i == 0) {
279
reverse(num.begin(), num.end());
10+
return;
2811
}
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+
}
3217
}
18+
reverse(num.begin() + i, num.end());
3319
}
34-
};
20+
};

0 commit comments

Comments
 (0)
0