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

describe

You are given two integer arrays nums1 and nums2, sorted in non-decreasing 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 non-decreasing 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], m = 3, nums2 = [2,5,6], n = 3 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 the 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 the 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 the 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 the code

parsing

Two sorted integer lists nums1 and nums2 are given, and two integers m and n represent the lengths of nums1 and nums2, respectively.

Instead of opening up new memory, the final sorted list is stored in the list NUMs1. The length of nums1 has been agreed to be m + n, where the first m elements represent valid elements to be merged, and the last n elements are set to 0 just for space, so nums2 can be put down after sorting.

In fact, this problem is relatively simple:

  • When n is 0, nums1 does not need to be merged with nums2, whatever nums1 is, just return nums1

  • If m is 0, nums1 is null and there are no elements to be merged. However, nums2 cannot be returned directly. Therefore, no matter how many elements nums2 has, nums1 should be assigned to nums1 and then nums1 should be returned

  • Compare the size backwards from the last valid element of nums1 to the last valid element of nums2:

    • If nums1[m-1] is greater than or equal to nums2[n-1], nums1[m-1] is assigned to nums1[m+n-1] and m is subtracted by one
    • Otherwise nums2[n-1] is assigned to nums1[m+n-1] and n is subtracted by one

  • If NUMs2 is iterated first, the rest of the elements in nums1 are sorted to begin with, so don’t worry about it. But if NUMs 1 is iterated first, maybe nums2 has the rest of the elements not iterated, because the rest of the elements in NUMs2 are sorted to begin with, Assign nums2[:n] to nums1[:n]

  • 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 in-place instead.
        """
        if n == 0: 
            return nums1
        if m == 0: 
            nums1[:n] = nums2[:n]
            return nums1
        while m>0 and n>0:
            if nums1[m-1]>=nums2[n-1]:
                nums1[m+n-1] = nums1[m-1]
                m -= 1
            else:
                nums1[m+n-1] = nums2[n-1]
                n -= 1
        nums1[:n] = nums2[:n]
        return nums1
                
                       	      
		
Copy the code

The results

Sorted Array for each node in the Python online submission list. Sorted Array for each node in the Python online submissions list.Copy the code

Original link: leetcode.com/problems/me…

Your support is my biggest motivation