首先，试验的时候要拿5个来试，3,4个都太少了。好久没做所以方法也忘了，是先从后往前找到第一个不合顺序的，然后在后面找到比这个大的最小的来交换，再把后面排序。
|
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
|
#include <algorithm>#include <vector>#include <climits>using
namespace
std;
bool
next_permutation(vector<int> &arr) {
bool
has_next = false;
int
size = arr.size();
int
i = arr.size() - 1;
while
(i - 1 >= 0) {
if
(arr[i-1] < arr[i]) {
has_next = true;
break;
}
i--;
}
if
(!has_next) return
false;
// find the min after i-1
int
min = INT_MAX;
int
minIdx = -1;
for
(int
j = i; j < size; j++) {
if
(arr[j] > arr[i-1] && arr[j] < min) {
min = arr[j];
minIdx = j;
}
}
int
tmp = arr[i-1];
arr[i-1] = arr[minIdx];
arr[minIdx] = tmp;
// sort elements from i
sort(arr.begin()+i, arr.end());
return
true;
} |