T31. Next Permutation【Medium】
题目
（注：这题建议先看例子）
实现 nextPermutation 方法，这个方法把输入的数字 a 中的每个数字重新排序得到一个恰好比当前数字大的数字 b，且其他大于 a 的排列也大于 b。如果不存在比 a 大的排列，就把 a 重新升序排列。
举个例子，还是例子好啊<(￣︶￣)>！
正确的变化就是这样的~
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
思路
建议直接看下面的代码和注释，然后举几个例子用下面的代码推导一遍就知道了~
推荐几种情况：① 231 ② 321 ③ 15243
代码
代码取自 Top Solution，稍作注释
public void nextPermutation(int[] A) {
if(A == null || A.length <= 1) return;
int i = A.length - 2;
// 从后往前找到第一个不符合降序的数字
while(i >= 0 && A[i] >= A[i + 1]) i--;
//如果不是整个数字降序执行
if(i >= 0) {
//从右往左找到一个比i对应的数字大的数
int j = A.length - 1;
while(A[j] <= A[i]) j--;
//交换i和j对应的数字
swap(A, i, j);
}
//把后段需要逆转的逆转一下，不仅逆转 4321 这样的，也逆转12543中的543
reverse(A, i + 1, A.length - 1);
}
//交换的方法，应该都懂吧..
public void swap(int[] A, int i, int j) {
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
//逆转的方法
public void reverse(int[] A, int i, int j) {
while(i < j) swap(A, i++, j--);
}
