[leetcode] 31. Next arrangement

31、 Next spread

subject ：

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 .

Their thinking ：

This question means ：

“ Next spread ” Is defined as ： The next larger order in the dictionary order of a given sequence of numbers . If there is no next larger arrangement , Then rearrange the numbers in the smallest order （ In ascending order ）.

We can formally describe the problem as ： Given several numbers , Combine them into an integer . How to rearrange these numbers , To get the next larger integer . Such as 123 The next larger number is 132. If there is no larger integer , The smallest integer is output .

With 1,2,3,4,5,6 For example , The order is ：

123456
123465
123546
...
654321

You can see such a relationship ：123456 < 123465 < 123546 < … < 654321.

The standard “ Next spread ” The algorithm can be described as ：

1. from Backward forward Find the first adjacent ascending element pair (i,j), Satisfy A[i] < A[j]. here [j,end) It must be in descending order
2. stay [j,end) Find the first satisfaction from back to front A[i] < A[k] Of k.A[i]、A[k] They are the above 「 decimal 」、「 Large number 」
3. take A[i] And A[k] In exchange for
4. It can be concluded that at this time [j,end) It must be in descending order , Inversion [j,end), In ascending order
5. If in step 1 No matching pair of adjacent elements found , Show the current [begin,end) For a descending order , Then jump to step 4

Reference code ：

public void nextPermutation(int[] nums) {
    
    int len = nums.length;
    for (int i = len - 1; i > 0; i--) {
    
            if (nums[i] > nums[i - 1]) {
    
                Arrays.sort(nums, i, len);
                for (int j = i; j <len; j++) {
    
                    if (nums[j] > nums[i - 1]) {
    
                        int temp = nums[j];
                        nums[j] = nums[i - 1];
                        nums[i - 1] = temp;
                        return;
                    }
                }
            }
        }
	Arrays.sort(nums);
	return;  
}