This is the 28th day of my participation in Gwen Challenge

preface

The next arrangement of question 31 is as follows:

To implement a function that gets the next permutation, the algorithm rearranges the given sequence of numbers into the next larger permutation in the lexicographical order.

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]

Example 2:

Input: nums = [3,2,1]

Example 3:

Input: nums = [1,1,5] output: [1,5,1]

Example 4:

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

A, thinking

Note: A larger arrangement means that the contents of the array remain the same and are just larger than the current arrangement, with no other arrangement in between. For example, the next permutation of 123 is 132 instead of 321

Let’s start by thinking about the next larger permutation of {2, 3, 4, 5, 2, 6, 5, 4, 3}.

The answer is: {2, 3, 4, 5, 3, 2, 4, 5, 6}

How do you do that? In fact, it is very simple, with the following two principles:

  1. Replace high to the right with as small a low as possible (low value > high value)
  2. After the substitution, sort from the highest level of the substitution in ascending order to the right (with large values to the right)

For example

Again, nums = {2, 3, 4, 5, 2, 6, 5, 4, 3} is used as an example to illustrate the above two principles

  1. It makes sense to replace the top right as much as possible becauseThe closer you go, the smaller you get.6, 5, 4, 3Is greater than2Which low position to choose? Of course it’s choice3So that we can make before2The range of change at the high of.
  2. The first step is going to benumsModified tonums = {2, 3, 4, 5, 3, 6, 5, 4, 2}. You’ll notice that from the substitution3On the right6, 5, 4, 2Is to place large values high, so need to useascendingPlace small values at high values. I’m going to replace3The one on the right is changed to2, 4, 5, 6
  3. Returns the resultnums = {2, 3, 4, 5, 3, 2, 4, 5, 6}Can be

Second, the implementation

The implementation code

Some notes: the implementation method and the idea of keeping the same, first find the replaceable high, then swap elements, and finally use ascending order to arrange the elements after the swap position

    public void nextPermutation(int[] nums) {
        // The first element represents the minimum replaceable high level
        int[] place = new int[] {Integer.MIN_VALUE, 0};
        // Find all replaceable positions from right to left
        for (int i=nums.length-1; i>0; i--) {
            // j is high
            for (int j=i-1; j>-1; j--) {
                // Replace the high right as much as possible
                if (nums[i] > nums[j] && j>place[0]) {
                    place[0] = j;
                    place[1] = i; }}}int begin =0;
        // If there is no exchange
        if (place[0] <= Integer.MIN_VALUE) {
            place[0] = 0;
        } else {
            // swap I j
            int temp = nums[place[0]];
            nums[place[0]] = nums[place[1]];
            nums[place[1]] = temp;
            // Swap elements
            begin = place[0] + 1;
        }

        // Bubble sort, I ~ j ascending order
        for (int i=begin; i<nums.length; i++) {
            for (int j=i+1; j<nums.length; j++) {
                if (nums[i] > nums[j]) {
                    // swap I j
                    inttemp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }}}}Copy the code

The test code

    public static void main(String[] args) {
        int[] nums = {2.3.4.5.2.6.5.4.3};
        new Number31().nextPermutation(nums);
        System.out.println(nums);
    }
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥