This is the 20th day of my participation in the August Text Challenge.More challenges in August

It’s Friday again. Every time it’s Friday, I will sigh how time flies. A week has passed, and every day is very busy, but it seems that the results are not obvious.

Yesterday and today no exercise for 2 days in a row, set the flag to fall down, the next time more to hold on this weekend, there are a lot of things haven’t finished, want to see of book, for example, about the communication, about the autopilot, and want to do next week 1 to share about the convertible bond, there are a lot of similar things. Weekends are very short, so hopefully this week will get all of these things done.

Fortunately, the habit of doing leetcode and text every day has not broken, especially yesterday I went home after 11 o ‘clock, and finally finished before 12 o ‘clock. Let’s continue today, problem 31 for Leetcode.

The title

To implement a function that gets the next permutation, the algorithm needs to rearrange a given sequence of numbers into the next larger permutation in lexicographical order (that is, to combine the next larger integer). If no next larger permutation exists, the numbers are rearranged into the smallest permutation (that is, ascending). You must modify in place, allowing only extra constant space.

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]

Example 4: Input: nums = [1] Output: [1]

Train of thought

Although the topic is to request a arrangement, we can regard as the next number better understand, consider an array from left to right a number that is on the left, on the right side of the low, the question is asked by the current number of characters of the smallest is larger than the current number of a number, if the current number is the number of characters to the largest number of the wheel back to the minimum.

So we can do this:

  1. From right to left, find the first number that is lower than the number on the right, subscript high
  2. From right to left, find the first number greater than num[high] with the subscript low
  3. Swap num[high] and num[low]
  4. Inversion of num [high + 1] ~ num [len – 1)

Of course, special cases should be dealt with first, if the first step can not find high, prove that the array is monotonically decreasing, has been the largest number of these arrays can represent, to turn back to the minimum, directly reverse can be.

Why can we do that? The way to think about it is, if we want to find a number that is larger than the current number, we have to have a higher number than the current number. After satisfying the larger premise, this value should be as small as possible, so the highest value of this value should be as far to the right as possible. We can assume that there is a subscript high, and the right side of high is a monotonically decreasing sequence. Then the numbers to the right of high will only be smaller, not larger, no matter how they are swapped. Therefore, high must be swapped. So which one do YOU want to swap? It’s got to be bigger than num[high] and as far to the right as possible. Why? Because the right side of high is a monotonically decreasing sequence, the value to the right is smaller. Now we know if we find a low that swaps with a high, but what about step 4? The reason for this is that if we swap the 1 bit of high for a larger value, whatever we do will be larger than the original value. In order to get the minimum value, we should arrange the value to the right of high from the smallest to the largest, until, before swapping, the right of high is a monotonically decreasing sequence, Num [low] is the first value on the right that is larger than num[high], so after switching, the right side of high is a monotonically decreasing sequence.

Java version code

class Solution { public void nextPermutation(int[] nums) { int len = nums.length; Int high = -1, low = -1; for (int i = len - 1; i > 0; i--) { if (nums[i-1] < nums[i]) { high = i - 1; break; Int left = 0, right = len-1; int left = 0, right = len-1; while (left < right) { swap(nums, left, right); left++; right--; } return; } for (int I = len-1; int I = len-1; i > high; i--) { if (nums[i] > nums[high]) { low = i; break; Swap (nums, high, low); swap(nums, high, low); int left = high + 1, right = len - 1; while (left < right) { swap(nums, left, right); left++; right--; } return; } private static void swap(int[] nums, int a, private static void swap(int[] nums, int a, int b) { nums[a] += nums[b]; nums[b] = nums[a] - nums[b]; nums[a] -= nums[b]; }}Copy the code