Question

Formatted question description: https://leetcode.ca/all/31.html

31	Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

    1,2,3 → 1,3,2
    3,2,1 → 1,2,3
    1,1,5 → 1,5,1

@tag-array

Algorithm

This question lets us find the next sort order. As can be seen from the example given in the question, if the given array is in descending order, it means that it is the last case of the full order, and the next order is the initial case. You can see The previous blog Permutations. Look at the following example again, there is an array as follows

1  2  7  4  3  1

The next arrangement is:

1  3  1  2  4  7

So how did we get it? By observing the original array, we can find that if we look forward from the end, the number gradually increases, and then decreases at 2, and then we look for the first number greater than 2 from the back, which is 3, then we exchange 2 and 3, and then transpose all the numbers after 3 at this time, the steps are as follows:

1  2  7  4  3  1

1  2  7  4  3  1

1  3  7  4  2  1

1  3  1  2  4  7

Code

Java

  • import java.util.Arrays;
    
    public class Next_Permutation {
    
        // time: O(N^2)
        // space: O(1)
        public class Solution {
    
            public void nextPermutation(int[] nums) {
    
                if (nums == null || nums.length == 0) {
                    return;
                }
    
                // 总体目标是,高位的小数字,换低位的大数字,才能得到next
                for (int i = nums.length - 2; i >= 0; --i) { // 3, 4, 5, 2, 1 // 注意. i < Len - 1. 也就是停在倒数第二个
                    if (nums[i] < nums[i + 1]) { // 第一个波峰波谷 => 4
                        for (int j = nums.length - 1; j > i; --j) {
                            if (nums[j] > nums[i]) {
                                // 找到第一个比nums-i大的数 => 5
                                swap(nums, i, j); // 3,5,4,2,1
    
                                // reverse 因为剩下部分肯定是从大到小
                                // 找到第一个比nums-i大的数的一步,相当于是排序,找insert position
                                reverse(nums, i + 1, nums.length - 1); // [4,2,1] reverse to [1,2,4] => 3, 5, 1, 2, 4
                                return;
                            }
                        }
    
                    }
                }
    
                reverse(nums, 0, nums.length - 1); // for没有return,就整个翻转
            }
    
            private void swap(int[] nums, int i, int j) {
    
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
    
            }
    
            private void reverse(int[] nums, int i, int j) {
    
                while (i < j) {
    
                    int tmp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = tmp;
    
                    i++;
                    j--;
                }
            }
        }
    }
    
  • Todo
    
  • class Solution(object):
      def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        if nums is None or len(nums) <= 1:
          return
    
        pos = None
        p = len(nums) - 2
        # find the first number that is not in correct order
        while p >= 0:
          if nums[p + 1] > nums[p]:
            pos = p
            break
          p -= 1
    
        if pos is None:
          self.reverse(nums, 0, len(nums) - 1)
          return
    
        # find the min value in the rest of the array
        minPos, minV = pos + 1, nums[pos + 1]
        for i in range(pos + 1, len(nums)):
          if nums[i] <= minV and nums[i] > nums[pos]:
            minV = nums[i]
            minPos = i
        # swap the two above number and reverse the array from `pos`
        nums[pos], nums[minPos] = nums[minPos], nums[pos]
        self.reverse(nums, pos + 1, len(nums) - 1)
    
      def reverse(self, nums, start, end):
        while start < end:
          nums[start], nums[end] = nums[end], nums[start]
          start += 1
          end -= 1
    
    

All Problems

All Solutions