Force buckle 31 next arrangement

Power button 31 Next spread

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 .

I/o sample

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

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

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

Topic analysis

The description of this question can only say , Said and didn't say the same , It's not clear at all . Let's reinterpret the topic . The input given in this topic is an array nums=[1,2,3], We need to find the next array .

Does it sound silly , But if you look at this array as a continuous number 123 Well , What we need to find is that we need to find exactly the right ratio 123 Large but not overly large arrays are 132

According to this principle, we can write the adjacency relation of this number , It is a process of size comparison

123
132
213
231
312
321

So how do you find the right permutation , We need to analyze the increasing law of these adjacency relations .

1. First of all, we should look from the back to the front , Find the first sequentially increasing number pair , such as 23
2. Record , Coordinates of the first value of the number pair i, from i+1, To end, Find the first greater than in reverse order nums[i] Coordinates of values j
3. In exchange for nums[i] and nums[j] Value
4. take i Subsequent numbers are sorted in ascending order
5. If the array inputs are all in reverse order , Then you can sort the original array incrementally .

Reference link

Algorithm implementation , Two scans

void nextPermutation(vector<int>&nums)
    {
    
        int length=nums.size();

        //  When the string length of the container is less than or equal to 1 when , No sorting 
        if(length<=1)
        {
    
            return;
        }

        // Find the first increment in the array 
        int i=length-2;
        for(i=length-2;i>=0;i--)
        {
    
            if(nums[i]<nums[i+1])
            {
    
                break;
            }
        }

        // When the sequence is found to be decreasing, the first increasing array is returned 
       if(i==-1)
        {
    
            sort(nums.begin(),nums.end());
        }
        else
        {
    
            // Find the first one greater than i Coordinates of the elements of 
            int pos;
            for( pos=length-1;pos>i;pos--)
            {
    
                if(nums[pos]>nums[i])
                {
    
                    break;
                }
            }
            swap(nums[i],nums[pos]);
            // Yes i The following elements are sorted incrementally 
            sort(nums.begin()+i+1,nums.end());
        }
    }