leetcode 31. Next Permutation（python）

This article has participated in 「 Digging force Star Program 」, Win a creative gift bag , Challenge creation incentive fund .

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 code 

Example 2:

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

Example 3:

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

Example 4:

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

Note:

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

analysis

According to the meaning , Is to give a list containing integer numbers nums , The elements of this list can form a number from left to right , We want to implement a function , take nums The number of the new list formed by rearranging the elements in is just as large as the initial number .

If such an arrangement is impossible to find , It must be rearranged in ascending order . And the problem requires that we can't use additional space , In other words, only in the original nums Operate on the list .

In fact, this problem can be solved by violence , But it takes too much time , I still don't recommend . In fact, this is a problem of finding rules , Suppose we now have a list [4,7,5,3] , The next list bigger than him should be [5, 3, 4, 7], The basic idea is to follow the smallest arrangement, that is, the ascending result of the list , The largest ranking is the result of the descending order of the list , The process is as follows ：

• Traverse from left to right , And then finally [3] , A single number does not operate
• The last two are [5,3] ,5 Greater than 3 , This sub list has been composed of the maximum number , No larger number can be found , So no operation
• The last three are [7,5,3], Same as above , No operation
• The last four are [4,7,5,3] , here 4 Less than 7 And less than 5 , and [4,7,5,3] The next order bigger than him should be [4,7,5,3] The smallest of a large set of results , So we should 4 and 5 Exchange to get [5,7,4,3] , here 5 In the first place , The following sub list should be minimized , namely [3,4,7], When stitched together, the final result is [5,3,4,7]

To sum up, the steps are ：

• Find the first descending numeric index from right to left i , The number in the example is 4
• Find the first ratio from right to left nums[i] Index of large numbers j , The number in the example is 5
• Exchange index i and j The elements of
• take nums[i+1:] The elements are arranged 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 code 

Running results

Runtime: 32 ms, faster than 58.10% of Python online submissions for Next Permutation.
Memory Usage: 13.3 MB, less than 71.68% of Python online submissions for Next Permutation.
 Copy code 

analysis

The above solution process should be very detailed , If you don't understand it, you can understand it by reading it more times , Only the code part implements several functions by itself , It seems more complicated , We can simplify , Use python It would be better to use the built-in function to solve the problem .

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 code 

Running results

Runtime: 28 ms, faster than 77.80% of Python online submissions for Next Permutation.
Memory Usage: 13.2 MB, less than 92.31% of Python online submissions for Next Permutation.
 Copy code 

Original link ：leetcode.com/problems/ne…

Your support is my greatest motivation