给定一个数组，求该数的序列的下一个序列。如果该序列已经是最后一个最大的序列了，输出最小的排序。
首先思路一定要清晰。
要找第一个值得交换的数——该数尽可能的靠近个位，且该数的前面存在一个数比该数大。然后找到前面那个比该数大的最小的数交换即可。
最后~该数前面的所有数升序排序。
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);
}
}
};
|