let 31 Next Permutation

参考博客: https://www.cnblogs.com/eudiwffe/p/6260699.html

主题思想: 构造下一个排列的思路如下:

  1. 从后往前找,找到第一个降序对(从后往前降序)出现的位置,比如 1,2,5,4,3 找到第一个出现a[i]
class Solution {
    public void nextPermutation(int[] nums) {

        if(nums==null||nums.length<=1)  return ;
        int n=nums.length;
        int i=n-1;
        int j=n-1;
        int k=n-1;
/*这里解释一下,如果是已经降序排列,或者非上升排列的话,这个循环里面的内容不会执行,也就是对数组里面数字全相等进行了处理,不用额外考虑,因为全相等是降序的一种形式 */
        for(j=n-1;j>0;j--){
            i=j-1;
            if(!(nums[i]<nums[j])) continue;

           //只要在循环里,意味着k一定存在且合法,
            for( k=n-1;k>=j;k--){
                if(nums[i]<nums[k]) break;
            }
            //swap
            swap(i,k,nums);
             reverse(j,n-1,nums);
            return ;

        }

        //reverse j--end
        reverse(0,n-1,nums);
        return ;

    }
    public  static void swap(int i,int j,int [] nums){
        int t=nums[i];
        nums[i]=nums[j];
        nums[j]=t;
    }
    public static void reverse(int low,int hi,int[] nums){
        if(hi<=low) return ;
        int t;
        while(low<hi){
            t=nums[low];
            nums[low]=nums[hi];
            nums[hi]=t;
            low++;
            hi--;
        }
    }
}
本站公众号
   欢迎关注本站公众号,获取更多程序园信息
开发小院