“This is the 20th day of my participation in the November Gwen Challenge. See details of the event: The Last Gwen Challenge 2021”.

Merge Sorted Array

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: ,2,3,0,0,0 nums1 = [1], m = 3, nums2 = [6] 2, n = 3 Output:,2,2,3,5,6 [1] 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. 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]. 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. Constraints: nums1.length == m + n nums2.length == n 0 <= m, n <= 200 1 <= m + n <= 200 -109 <= nums1[i], nums2[j] <= 109 Follow up: Can you come up with an algorithm that runs in O(m + n) time?Copy the code

Demand analysis

1. Ordered arrays

Nums1 >=m; nums1>=m

3. The prompt boundary value is not considered for the time being

4. There is no need to return, just make nums1 an ordered array

Their thinking

Take advantage of data types in Python:

List supports del to delete elements, extend(seq) to append sequence elements, index to find element indexes, and slice to replace elements

The next step is relatively simple, and the code takes care of the rest

Code implementation

Mistake # 1:
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        while m>0:
            if 0 in nums1:
                del nums1[nums1.index(0)]
                m-=1
        nums1.extend(nums2)
        nums1.sort()
Copy the code

Analysis: Not considering nums1=[1],m=1 use case, trapped in a loop

Correct Case # 2:
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        l=len(nums1)
        while l>m:
            if 0 in nums1:
                del nums1[nums1.index(0)]
                l-=1
        nums1.extend(nums2)
        nums1.sort()
Copy the code

Analysis: using the second point of requirements analysis, nums1 array length is greater than or equal to m, then out of the loop condition nums1 is equal to m, just stop traversal

Correct Case # 3:

The above code is still a bit verbose, and while it's easier to understand, testing should take less code to implement

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        nums1[m:]=nums2
        nums1.sort()
Copy the code

Len (nums1)=m, len(nums1)=m, len(nums1)=m, len(nums1)=m, len(nums1)=m, len(nums1)=m, len(nums1)=m, len(nums1)=m, len(nums1)=m, len(nums1)=m, len(nums1)=m

conclusion

1. The idea of solving the problem is very clear, using the features of Python data types to solve the problem

2. From the perspective of execution efficiency, the same code may be executed at different times and may see different times; This is all about the performance of the machine

3, or continue to talk about the algorithm to solve the problem, suggest to see more, understand other people’s excellent problem solving ideas