当前位置：网站首页>Leetcode t31: next spread

Leetcode t31: next spread

2022-07-01 08:17:00 【Fan Qianzhi】

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]

Tips

1 <= nums.length <= 100
0 <= nums[i] <= 100

Ideas

First, look from right to left , Find a subscript $i n d$ , Make all the numbers on the right of it in descending order . for example :

↓
1432, ind=0

And then , stay $[i n d + 1, n u m s . l e n g t h - 1]$ Choose a book that is the smallest and greater than $a [i n d]$ Number of numbers , And $a [i n d]$ Swap places , And will $i n d$ The numbers on the right are arranged in ascending order .

Code

    int findInd(int[] a) {
     //  Look from right to left , Find a subscript , All the numbers on the right are from big to small , Such as 1.432,
        //  that , Need from 432（ That is, find the smallest of all the numbers in reverse order , namely 2）, Replace 1, And let 143 Ascending order 
        int ind = a.length-1;
        while(ind > 0) {
    
            if(a[ind] <= a[ind-1]) ind--;
            else break;
        }
        return ind-1;
	}
	
	void next_permutation(int[] a) {
    
		int ind = findInd(a);
		if(ind == -1) {
    
			Arrays.sort(a);
		}
		else {
    
			int tar = -1;
			for(int i = a.length-1; i > ind; i--) {
    
				if(a[i] > a[ind]) {
    
					tar = i;
					break;
				}
			}
			int t = a[ind]; a[ind] = a[tar]; a[tar] = t;
			Arrays.sort(a, ind+1, a.length);
		}
	}