31. Next arrangement

One 、 Title Description

An integer array array Is to arrange all its members in sequence or linear order .

• for example ,arr = [1,2,3] , The following can be regarded as arr Permutation ：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] .

Integer array Next spread It refers to the next lexicographic order of its integers . More formally , Arrange all the containers in the order from small to large , So the array of Next spread It is the arrangement behind it in this ordered container . If there is no next larger arrangement , Then the array must be rearranged to the lowest order in the dictionary （ namely , Its elements are arranged in ascending order ）.

• for example ,arr = [1,2,3] The next line up for is [1,3,2] .
• Similarly ,arr = [2,3,1] The next line up for is [3,1,2] .
• and arr = [3,2,1] The next line up for is [1,2,3] , because [3,2,1] There is no greater order of dictionaries .

Give you an array of integers nums , find nums The next permutation of .

must In situ modify , Only additional constant spaces are allowed .

Example 1：

 Input ：nums = [1,2,3]
 Output ：[1,3,2]

Example 2：

 Input ：nums = [3,2,1]
 Output ：[1,2,3]

Example 3：

 Input ：nums = [1,1,5]
 Output ：[1,5,1]

Two 、 Problem solving

Two traversal

class Solution {
    
    public void nextPermutation(int[] nums) {
    
        // You need to find the first ascending subscript from the back 
        int length = nums.length;
        int end = length-2;
        // If the current value is greater than the following value , Keep looking for , Always find the first ascending subscript 
        while(end >= 0 && nums[end] >= nums[end+1]){
    
            end--;
        }

        // After finding the subscript value , Find a value greater than the subscript value after 
        // Pay attention to the boundary conditions 
        if(end >= 0){
    
            int next = length - 1;
            while(next >= 0 && nums[end] >= nums[next]){
    
                next--;
            }
            swap(nums,end,next);
        }
        reverse(nums,end+1);
        
    }
    public void swap(int[] nums,int left,int right){
    
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }

    public void reverse(int[] nums,int left){
    
        int right = nums.length-1;
        while(left <= right){
    
            swap(nums,left,right);
            left++;
            right--;
        }
    }
}