“This is the 15th day of my participation in the First Gwen Challenge 2022.First challenge in 2022”.

Topic describes

One arrangement of an array of integers is to arrange all its members in sequential or linear order.

Arr = [1, 2, 3], for example, the following can be regarded as the arrangement of arr: [1, 2, 3], [31] 1,,1,2 [3], [2,3,1]. The next permutation of an integer array is the next lexicographically larger permutation of its integers. More formally, if all the permutations of an array are arranged in a container according to their lexicographical order, the next permutation of the array is the one following it in the ordered container. If there is no next larger permutation, then the array must be rearranged to the lexicographically smallest permutation (that is, its elements are sorted in ascending order).

For example, the next permutation of arr = [1,2,3] is [1,3,2]. Similarly, the next permutation of arr = [2,3,1] is [3,1,2]. The next permutation of arr = [3,2,1] is [1,2,3], because [3,2,1] does not exist as a lexicographically larger permutation. Given an integer array nums, find the next permutation of nums.

You must modify in place, allowing only extra constant space.

Example 1:

Input: nums = [1,2,3]Copy the code

Example 2:

Input: nums = [3,2,1]Copy the code

Example 3:

Input: nums = [1,1,5] output: [1,5,1]Copy the code

Tip:

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

Subject link: Next permutation

Thinking is introduced

For example, 2, 6, 3, 5, 4, 1, we want to find the next permutation that’s just bigger than it is, so we can go back and see if we can make a bigger permutation with 4, 1, and the answer is no, and the same goes for 5, 4, 1 until 3, 5, 4, 1, Since 3 is less than 5, we can get the next permutation by rearranging this number because we want to make the new permutation as small as possible, so we go back and find the first number that is larger than 3, and we find 4 and then we switch the 3 and the 4, We get 4, 5, 3, 1 because we want to make the new sequence as small as possible, so we can sort 5, 3, 1, and we can see that in this algorithm, we get the end number in reverse order, so we just have to reverse it and finally, So we have 4, 1, 3, 5 and the complete sequence is 2, 6, 4, 1, 3, 5

Find the largest index k that is equal to nums[k] < nums[k+1]. Nums [l] > nums[k]; Swap nums[l] and NUMs [k]; Finally, flip nums[k+1:].

code

class Solution { public void nextPermutation(int[] nums) { if (nums == null || nums.length == 0) return; int firstIndex = -1; for (int i = nums.length - 2; i >= 0; i--) { if (nums[i] < nums[i + 1]) { firstIndex = i; break; } } if (firstIndex == -1) { reverse(nums, 0, nums.length - 1); return; } int secondIndex = -1; for (int i = nums.length - 1; i >= 0; i--) { if (nums[i] > nums[firstIndex]) { secondIndex = i; break; } } swap(nums, firstIndex, secondIndex); reverse(nums, firstIndex + 1, nums.length - 1); return; } private void reverse(int[] nums, int i, int j) { while (i < j) { swap(nums, i++, j--); } } private void swap(int[] nums, int i, int i1) { int tmp = nums[i]; nums[i] = nums[i1]; nums[i1] = tmp; }}Copy the code

The results

Result: Yes

Execution time: 7 ms,

Memory consumption: 41.7 MB

\