current position：Home>leetcode 88. Merge Sorted Array（python）
leetcode 88. Merge Sorted Array（python）
20220129 20:22:54 【Wang Daya】
This article has participated in 「 Digging force Star Program 」, Win a creative gift bag , Challenge creation incentive fund .
describe
You are given two integer arrays nums1 and nums2, sorted in nondecreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in nondecreasing order.
The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
Example 1:
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.
Copy code
Example 2:
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].
Copy code
Example 3:
Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.
Copy code
Note:
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
10^9 <= nums1[i], nums2[j] <= 10^9
Copy code
analysis
According to the meaning , Is to give a list of two ordered integers nums1 and nums2 , And give two integers m and n , They represent nums1 and nums2 The length of , The title requires us to merge these two ordered integer lists , Returns a list of integers in ascending order .
The final sorted list does not open up new memory space , It's stored in a list nums1 in . Because it has been agreed in the title nums1 The length of is m + n, The top m Elements represent the valid elements to be merged , after n The elements are set to 0 Just to occupy a seat , take nums2 integrate into nums1 After sorting, you can just put down .
In fact, the idea of this question is relatively simple ：

When n by 0 When , Express nums1 You don't need to be with nums2 A merger , No matter nums1 What is it , Go straight back to nums1 That's all right.

When m by 0 When , Express nums1 It's empty , There are no elements to merge , But you can't directly return to nums2 , Because the title requires that the last thing to return is nums1 , So no matter nums2 How many elements are there , Directly assign to nums1 , And then back again nums1 Can only be

from nums1 The last valid element of and nums2 The last valid element of starts the inverse comparison of size ：
 If nums1[m1] Greater than or equal to nums2[n1] , Will nums1[m1] Assign a value to nums1[m+n1] , meanwhile m Minus one
 Otherwise it would be nums2[n1] Assign a value to nums1[m+n1] , meanwhile n Minus one

If nums2 End of traversal first , because nums1 The remaining elements are ordered from the beginning , So leave him alone , But if nums 1 End of traversal first , Probably nums2 There are other elements that have not been traversed , because nums2 The remaining elements are ordered from the beginning , Direct will nums2[:n] Assign a value to nums1[:n] that will do

return nums1
answer
class Solution(object):
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: None Do not return anything, modify nums1 inplace instead.
"""
if n == 0:
return nums1
if m == 0:
nums1[:n] = nums2[:n]
return nums1
while m>0 and n>0:
if nums1[m1]>=nums2[n1]:
nums1[m+n1] = nums1[m1]
m = 1
else:
nums1[m+n1] = nums2[n1]
n = 1
nums1[:n] = nums2[:n]
return nums1
Copy code
Running results
Runtime: 38 ms, faster than 20.56% of Python online submissions for Merge Sorted Array.
Memory Usage: 13.6 MB, less than 16.74% of Python online submissions for Merge Sorted Array.
Copy code
Original link ：leetcode.com/problems/me…
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/202201292022523583.html
The sidebar is recommended
 Compile D + +, and use d to call C from python
 Install tensorflow and python 3.6 in Windows 7
 Python collects and monitors system data  psutil
 Python collects and monitors system data  psutil
 Finally, this Python import guide has been sorted out. Look!
 Quickly build Django blog based on function calculation
 Getting started with Python  object oriented  special methods
 Teach you how to use Python to transform an alien invasion game
 You can easily get started with Excel. Python data analysis package pandas (VI): sorting
 Implementation of toplevel design pattern in Python
guess what you like

Using linear systems in python with scipy.linalg

Python tiktok 5000+ V, and found that everyone love this video.

Using linear systems in python with scipy.linalg

How to get started quickly? How to learn Python

Modifying Python environment with Mac OS security

You can easily get started with Excel. Python data analysis package pandas (XI): segment matching

Advanced practical case: Javascript confusion of Python anti crawling

Better use atom to support jupyter based Python development

Better use atom to support jupyter based Python development

Fast power modulus Python implementation of large numbers
Random recommended
 Python architects recommend the book "Python programmer's Guide" which must be read by selfstudy Python architects. You are welcome to take it away
 Decoding the verification code of Taobao slider with Python + selenium, the road of information security
 Python game development, pyGame module, python implementation of skiing games
 This paper clarifies the chaotic switching operation and elegant derivation of Python
 You can easily get started with Excel. Python data analysis package pandas (3): making score bar
 Test Development: self study Dubbo + Python experience summary and sharing
 Python + selenium automated test: page object mode
 You can easily get started with Excel. Python data analysis package pandas (IV): any grouping score bar
 Opencv skills  saving pictures in common formats as transparent background pictures (with Python source code)  teach you to easily make logo
 You can easily get started with Excel. Python data analysis package pandas (V): duplicate value processing
 Python ThreadPoolExecutor restrictions_ work_ Queue size
 Python generates and deploys verification codes with one click (Django)
 With "Python" advanced, you can catch all the advanced syntax! Advanced function + file operation, do not look at regret Series ~
 At the beginning of "Python", you must see the series. 10000 words are only for you. It is recommended to like the collection ~
 [Python kaggle] pandas basic exercises in machine learning series (6)
 Using linear systems in python with scipy.linalg
 The founder of pandas teaches you how to use Python for data analysis (mind mapping)
 Using Python to realize national secondhand housing data capture + map display
 Python image processing, automatic generation of GIF dynamic pictures
 Pandas advanced tutorial: time processing
 How to make Python run faster? Six tips!
 Django: use of elastic search search system
 Fundamentals of Python I
 Python code reading (chapter 35): fully (deeply) expand nested lists
 Python 3.10 official release
 Solution of no Python 3.9 installation was detected when uninstalling Python
 This pandas exercise must be successfully won
 [Python homework] coupling network information dissemination
 Python application software development tool  tkinterdesigner v1.0 5.1 release!
 [Python development tool Tkinter designer]: Lecture 2: introduction to Tkinter designer's example project
 [algorithm learning] sword finger offer 64 Find 1 + 2 +... + n (Java / C / C + + / Python / go / trust)
 leetcode 58. Length of Last Word（python）
 Problems encountered in writing the HTML content of articles into the database during the development of Django blog
 leetcode 1261. Find Elements in a Contaminated Binary Tree（python）
 [algorithm learning] 1486 Array XOR operation (Java / C / C + + / Python / go / trust)
 Understand Python's builtin function and add a print function yourself
 Python implements JS encryption algorithm in thousands of music websites
 leetcode 35. Search Insert Position（python）
 leetcode 1829. Maximum XOR for Each Query（python）
 [introduction to Python visualization]: 12 small examples of complete data visualization, taking you to play with visualization ~