current position:Home>leetcode 31. Next Permutation(python)
leetcode 31. Next Permutation(python)
2022-01-30 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 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
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 python-3 character string
- Python pyplot draws a parallel histogram, and the x-axis 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 built-in 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 object-oriented programming
- Python notes (13): operations such as object-oriented programming
- Python notes (12): inheritance such as object-oriented programming
- Chapter 2: Fundamentals of python-5 Boolean
- Python notes (11): encapsulation such as object-oriented programming
- Python notes (10): concepts such as object-oriented 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