Force button 31. Next arrangement -- double finger needling

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 .

link ：https://leetcode.cn/problems/next-permutation

Example ：

analysis

[1 , 2 , 3] There are six ways of arrangement that can be formed
[1, 2 , 3] 、[1,3,2] 、[2,1,3] [2,3,1] [3,1,2] [3,2,1]
arr = [1,2,3] The next line up for is [1,3,2]
We can think of it as finding a number composed of elements in the array , In all combinations of numbers , It is composed of elements that are larger than the original array and are the closest to the original array .
123<132<213<231<312<321

for example arr = [ 1,2,4,3 ] The next order of is [1,3,2,4]
stay 1,2,3,4 The number that can be composed of these four numbers
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1
For the solution of this problem , I use double pointer ：
Define two pointers Respectively i and j
Both of them point to the last number of the array

Both pointers traverse forward , Find the pointer i The corresponding value is larger than the pointer j Corresponding value hours , Exchange data


Obviously 1243<1324<1342
So after the exchange, the number after the pair （i+1 To the last ） Perform an ascending process
Get data [1,3,2,4]

When the element is already the maximum , Back to the first , That is to sort the elements to get an array

Code

class Solution {
    
    public void nextPermutation(int[] nums) {
    

       for(int i=nums.length-1;i>=0;i--){
    
           for(int j=nums.length-1;j>i;j--){
    
           		// Data exchange 
               if(nums[i]<nums[j]){
    
                   int temp = nums[i];
                   nums[i] = nums[j];
                   nums[j] = temp;
                   //  An array nums Of i+1 Item to nums.length Sort items in ascending order 
                   Arrays.sort(nums,i+1,nums.length);
                   return;
               }
           }
       }
       // If two for Cycle down and don't find (nums[i]<nums[j]) The situation of , Sort the array in ascending order and return 
       Arrays.sort(nums);
    }
}

The time complexity is O（n）