current position：Home>leetcode 31. Next Permutation（python）
leetcode 31. Next Permutation（python）
20220130 13:22:25 【Wang Daya】
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 inplace 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 builtin 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 inplace instead.
"""
i = len(nums)1
while i>0:
if nums[i1]<nums[i]:
break
i = i1
i = i1
j = len(nums)1
while j>i:
if nums[j]>nums[i]:
break
j=j1
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
copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201301322222841.html
The sidebar is recommended
 Python code reading (Part 44): find the location of qualified elements
 Elegant implementation of Django model field encryption
 40 Python entry applet
 Pandas comprehensive application
 Chapter 2: Fundamentals of python3 character string
 Python pyplot draws a parallel histogram, and the xaxis value is displayed in the center of the two histograms
 [Python crawler] detailed explanation of selenium from introduction to actual combat [1]
 Curl to Python self use version
 Python visualization  3D drawing solutions pyecharts, Matplotlib, openpyxl
 Use python, opencv's meanshift and CAMSHIFT algorithms to find and track objects in video
guess what you like

Using python, opencv obtains and changes pixels, modifies image channels, and trims ROI

[Python data collection] university ranking data collection

[Python data collection] stock information collection

Python game development, pyGame module, python takes you to realize a magic tower game from scratch (2)

Python solves the problem of suspending execution after clicking the mouse in CMD window (fast editing mode is prohibited)

[Python from introduction to mastery] (II) how to run Python? What are the good development tools (pycharm)

Python type hints from introduction to practice

Python notes (IX): basic operation of dictionary

Python notes (8): basic operations of collections

Python notes (VII): definition and use of tuples
Random recommended
 Python notes (6): definition and use of lists
 Python notes (V): string operation
 Python notes (IV): use of functions and modules
 Python notes (3): conditional statements and circular statements
 Python notes (II): lexical structure
 Notes on python (I): getting to know Python
 [Python data structure series]  tree and binary tree  basic knowledge  knowledge point explanation + code implementation
 [Python daily homework] Day7: how to combine two dictionaries in an expression?
 How to implement a custom list or dictionary in Python
 15 advanced Python tips for experienced programmers
 Python string method tutorial  how to use the find() and replace() functions on Python strings
 Python computer network basics
 Python crawler series: crawling global airport information
 Python crawler series: crawling global port information
 How to calculate unique values using pandas groupby
 Application of builtin distribution of Monte Carlo simulation SciPy with Python
 Gradient lifting method and its implementation in Python
 Pandas: how to group and calculate by index
 Can you create an empty pandas data frame and fill it in?
 Python basic exercises teaching! can't? (practice makes perfect)
 Exploratory data analysis (EDA) in Python using SQL and Seaborn (SNS).
 Turn audio into shareable video with Python and ffmpeg
 Using rbind in python (equivalent to R)
 Pandas: how to create an empty data frame with column names
 Talk about quantifying investment using Python
 Python, image restoration in opencv  CV2 inpaint
 Python notes (14): advanced technologies such as objectoriented programming
 Python notes (13): operations such as objectoriented programming
 Python notes (12): inheritance such as objectoriented programming
 Chapter 2: Fundamentals of python5 Boolean
 Python notes (11): encapsulation such as objectoriented programming
 Python notes (10): concepts such as objectoriented programming
 Gradient lifting method and its implementation in Python
 Van * Python  simple crawling of a site course
 Chapter 1 preliminary knowledge of pandas (list derivation and conditional assignment, anonymous function and map method, zip object and enumerate method, NP basis)
 Nanny tutorial! Build VIM into an IDE (Python)
 Fourier transform of Python OpenCV image processing, lesson 52
 Introduction to python (III) network request and analysis
 China Merchants Bank credit card number recognition project (Part I), python OpenCV image processing journey, Part 53
 Python practice  capture 58 rental information and store it in MySQL database