This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

describe

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

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

The replacement must be in place and use only constant extra memory.

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

Input: nums = [1]
Output: [1]
Copy the code

Note:

1 <= nums.length <= 100
0 <= nums[i] <= 100
Copy the code

parsing

Given a list of integer numbers, nums, the elements of the list form a number from left to right. We want to implement a function that rearranges the elements of the list to form a number that is just larger than the original number.

If such a arrangement is impossible to find, it must be rearranged into an ascending order. And they tell us that we can’t use extra space, which means we can only operate on the original NUMS list.

In fact, this problem can be solved by brute force, but it takes too long and is not recommended. If we have a list [4,7,5,3], the next list larger than it should be [5, 3, 4,7]. The basic idea is to follow the smallest list ascending result, the largest list descending result.

  • Traverses from left to right, with the last digit [3], and does not operate on a single digit
  • The last two digits are [5, 3], and 5 is greater than 3. This sublist already consists of the maximum number, and no larger number can be found, so no operation is performed
  • The last three digits are [7,5,3], which is the same as above
  • The last four digits are [4, 7, 5, 3], where 4 is less than 7 and less than 5, and the next permutation larger than [4, 7, 5, 3] should be the smallest in the result set larger than [4, 7, 5, 3], so 4 and 5 should be swapped to get [5, 7, 4, 3], The following sublist should be minimized to [3,4,7], resulting in [5, 3,4,7].

In summary, the steps are:

  • Find the first descending numeric index I from right to left, which in this case is 4
  • Find the index j from right to left of the first number greater than nums[I], which in this case is 5
  • Swap the elements of indexes I and j
  • Sort the elements of nums[I +1:] in ascending order

answer

class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        i = len(nums) - 2
        while i>=0 and nums[i] >= nums[i+1]:
            i -= 1
        if i>=0: 
            j = len(nums)-1
            while (nums[j]<=nums[i]):
                j -= 1
            self.swap(nums, i, j)
        self.reverse(nums, i+1)
    
    def reverse(self, nums, start):
        i = start
        j = len(nums)-1
        while (i<j):
            self.swap(nums, i, j)
            i+=1
            j-=1
            
    def swap(self, nums, i, j):
        nums[i], nums[j] = nums[j], nums[i]
        
        
    

        	      
		
Copy the code

The results

Given in the Python online submission for Next Permutation. Given in the Python online submission for Next Permutation.Copy the code

parsing

The above solution process should be very detailed, do not understand several times to understand, but the code part of its own implementation of several functions, it seems cumbersome, we can simplify, use Python built-in functions to solve the problem better.

answer

class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        i = len(nums)-1
        while i>0:
            if nums[i-1]<nums[i]:
                break
            i = i-1
        i = i-1
        j = len(nums)-1
        while j>i:
            if nums[j]>nums[i]:
                break
            j=j-1
        nums[i],nums[j]=nums[j],nums[i]  
        nums[i+1:]=sorted(nums[i+1:]) 
Copy the code

The results

Given the linked link in the Python online submission. Memory Usage: 10 ms Given in the Python online submissions for Next Permutation.Copy the code

Original link: leetcode.com/problems/ne…

Your support is my biggest motivation