每天一题LeetCode【第23天】

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--);
}