LeetCode32——next permutation

This is a topic about array arrangement , The questions are as follows ：

in fact , be familiar with C++ STL As soon as my friend saw this problem , It should be thought of as STL A generic algorithm already provided in . stay STL The algorithm function in is completely consistent with that described in this question , But in STL The return value in is bool type , If there's a bigger next permutation , So return true, And change the container to the next larger arrangement .C++ Primer 5th edition The appendix is explained as follows ：

So in fact, this problem is AC The code is …

// using STL generic algorithm directly, hahaha... 
next_permutation(nums.begin(), nums.end());

Personal test , This is really passable ：）
Okay , Now let's talk about the solution of this problem , First, I list them in order 123 The combination of these three numbers , From top to bottom is the order that should be returned ：

123
132
213
231
312
321

I have to say that this problem is still a little difficult , It's hard to explain the underlying principles or mysteries . This time it will be a tree hole , Roughly describe the algorithm flow , On the one hand, it deepens the right STL Understanding of algorithm implementation in , Also for future review , following end Represents the index of the last element ：

1. Make i Traverse the sequence from back to front , Find the first satisfaction nums[i] < nums[i+1] The element subscript of i, At the same time, we can infer [i+1,end] Are all descending sequences . If i<0, Indicates that the current sequence is completely descending , The maximum dictionary order has been reached , Direct transfer 4, Otherwise execution 2,3,4.
2. Make j Traverse the sequence from back to front again , Find the first satisfaction nums[i] < nums[j] The element subscript of j.
3. Exchange elements nums[i] and nums[j].
4. The sequence of [i+1, end] Partially reversed .

The idea of this algorithm is to ensure the exchange number pairs found as much as possible (nums[i], nums[j]) yes The closest numerical And Closest to the end , After the exchange is completed, the ascending order of the sequence is guaranteed by inversing the data after the exchange point , Ascending order is the case that is closest to the next lexicographic order .

The complete code is as follows ：

class Solution {
    
    /*swap the two elements in vector, i & j are index*/
    void swap(vector<int>&nums, int i, int j)
    {
       
        if(i == j)
            return;

        /*intermediate variable*/ 
        int Temp;
        Temp = nums[i], nums[i] = nums[j], nums[j] = Temp;
    }

    /*reverse the whole vector to get the min permutation*/
    void reverse(vector<int>& nums, int h, int t)
    {
    
        int Head = h, Tail = t;
        while(Head <= Tail)
            swap(nums, Head++, Tail--);
    }

public:
    void nextPermutation(vector<int>& nums) {
    
        // using STL generic algorithm directly, hahaha... 
        // next_permutation(nums.begin(), nums.end());
        if(nums.size() == 1)
            return;

        int Tail = nums.size() - 2, SearchBigger = nums.size() - 1;
        /*find the element's index Tail which satisfies nums[i] < nums[i + 1]*/
        /*Tail is as big as possible*/
        while(Tail >= 0 && nums[Tail] >= nums[Tail + 1] )
            --Tail;
        
        /*if the element can be found, then search the closest bigger element*/
        if(Tail >= 0)
        {
    
            while(SearchBigger > Tail && nums[SearchBigger] <= nums[Tail])
                --SearchBigger;
            swap(nums, SearchBigger, Tail);
        }
        
        /*reverse the array[Tail+1, End] to get ready for next permutation*/
        reverse(nums, Tail + 1, nums.size() - 1);
    }
};

This algorithm still needs to be considered repeatedly