Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities

I. Title Description:

Next permutation

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.

Ii. Ideas and Implementation:

Ideas:

In digital sequence [1, 2, 3], for example, it is arranged according to the dictionary sequence in the order: [1, 2, 3] 31 [1] [2,1,3],3,1 [2] [3,1,2] [3, 2, 1]

How to make it bigger: Pick a larger number from the lower position and swap the smaller number in front. The increase should be as small as possible.

Something like [3,2,1] which is decreasing, without the next permutation, is already stable and can’t get bigger.

Like 1,5,2,4,3,2, why do they get a little bigger?

Go from right to left, look for the first number that is smaller than the neighbor on the right, and switch it back

“First” means as low as possible, and “smaller than the right neighbor” means it’s the first trough from right to left

For example, 1, 5 (2), 4, 3, 2, this 2 in the middle.

And then we go from right to left again, and we look for the first number that’s greater than 2. 15 (2) 4 (3) 2, after switching: 15 (3) 4 (2) 2.

It’s not over! The magnitude of the increase can be a little bit smaller, the decimal is a little bit bigger, the last three can be a little bit smaller.

The last three digits are definitely decreasing. Flip it and become [1,5,3,2,2,4].

Code implementation:

function nextPermutation(nums) { let i = nums.length - 2; While (I >= 0 && nums[I] >= nums[I +1]) {// Find the first number less than the right neighbor I --; } if (I >= 0) {if (I >= 0) {if (I >= 0) {if (I >= 0) {if (I >= 0) {if (I >= 0) {if (I >= 0) { While (j >= 0 &&nums [j] <= nums[I]) {// Find the first number j greater than nums[I]; } [nums[i], nums[j]] = [nums[j], nums[i]]; Let l = I + 1; let l = I + 1; let l = I + 1; let r = nums.length - 1; While (l < r) {// nums[l], nums[r]] = [nums[r], nums[l]]; l++; r--; }}Copy the code

Iii. Summary:

The key is to solve the problem: pick a larger number from the lower position and swap the smaller number. The increase should be as small as possible.