下一個排列（Leetcode31）解讀

本題代碼來自Leetcode官方，個人對其了解後，生成自己的注解，以便更好的讓讀者了解。如有侵權，立即删除！

public class Main31 {

    public static void main(String[] args) {
        int[] arr = new int[]{9, 5, 3, 1};
        nextPermutation(arr);
    }

    /**
     * 核心思想：給定一個降序則該序列沒有可能有下一個更大的排列；
     * 1.從給定數組的右側掃描出第一個a[i-1]<a[i]; （違背了核心思想，是以處理）
     * 2.對a[i-1]固定位置，從其右側（從右到左）找出第一個比a[i-1]大的數字a[j]；
     * 3.交換a[i-1]和a[j]的值。此時a[i-1]位置是下一個更大元素的首位，也是未交換之前a[i-1]到右側最後一位組成數的下一個比起大的數的首位；
     * 4.将a[i-1]右側重新排列為最小（升序，之前的降序）；此時，構成的數是原數下一個比其大的數；
     * @param nums
     */
    public static void nextPermutation(int[] nums) {
        int i = nums.length-1;  //倒數第1個元素下标

        while(i-1 >= 0 && nums[i] <= nums[i-1]){ /*确定nums[i-1]的位置，即nums[i-1]<nums[i],簡化為确定i-1的位置*/
            i--;
        }
        if(i-1 >= 0){  /*如果i位置還在數組中，即nums[i-1]<nums[i]*/  /*i不在數組的情況就是遇到了一降序數組，直接反轉讓其成一個最小數列*/
            int j = nums.length-1;   /*定位j到i的右側區域的最右側*/
            while(j >= 0 && nums[j] <= nums[i-1]){  /*找到nums[j]第一次大于nums[i-1]的位置，此時要滿足j也要在數組中（當然，j肯定在數組中）*/
                j--;   /*j停下來的位置就是第一次大于nums[i-1]的位置*/
            }
            swap(nums,i-1,j);  /*交換nums[i-1],nums[j]的值*/
        }
        reverse(nums,i); /*反轉i右側的降序，轉變為升序*/
    }

    private static void reverse(int[] nums, int start) {
        int i = start;
        int j = nums.length-1;
        while (i < j){
            swap(nums,i,j);
            i++;
            j--;
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}      

轉載于:https://www.cnblogs.com/startelk/p/11305980.html