[LeetCode] question 88: merge two ordered arrays

Title:

Give two ordered integer arrays nums1 and nums2, and two integers m and n, representing the number of elements in nums1 and nums2 respectively

Please merge nums2 into nums1 so that the merged array is also arranged in order

Note: the merged array should not be returned by the function, but stored in the array nums1. It is assumed that the initial length of nums1 is m+n, where the first m elements represent the elements to be merged, the last n elements are 0, and the length of nums2 is n

Title Link: Merge two ordered arrays

Topic limitations:

After merging, it is also sorted in ascending order

nums2 merged after nums1

An algorithm with time complexity O (m+n) is designed and implemented

Problem solving ideas:

Idea 1: reorder after consolidation

The time complexity is O ((m+n) log (m+n))

The space complexity is O (log (m+n))

Idea 2: copy array 1 and use double pointer sorting to traverse into nums1

The p1 pointer copies nums1, and the p2 pointer traverses nums2

Compare the element sizes of p1 and p2 pointers, load nums1 from small to large, and overwrite the functions inside

Because the title gives the number of elements with m as nums1, the initial length of nums1 is m+n, there are only m actual elements, and the rest are 0 (n, which should be ignored)

Affected by the sorted condition, the elements in nums1 array are arranged in order, and m elements are filled with 0

In fact, it can be understood that the length of nums1 array is only m and there are only m elements

Therefore, in the process of p1 traversing the copied nums1, there is no need to consider the comparison between p2 after m elements and 0 after m elements in nums1

However, the disadvantage of this idea is that both nums1 and nums2 need to be traversed to end

Therefore, the time complexity is O (m+n) and the space complexity is O (m+n)

Idea 3: double pointer reverse traversal, sorting and merging in nums1

On the basis of idea 2, cancel the temporary array, combined with the characteristics that the initial length of nums1 is m+n, use the double pointer method to traverse nums2 in reverse while adding the compared elements to nums1

Set p1 and p2 as the last element of nums1 and nums2

At any time during traversal:

There are m-1-p1 elements in the nums1 array that are placed in the second half of nums1

n-1-p2 elements in nums2 array are placed in the second half of nums1

After the pointer P1, if the nums1 array has m+n-p1-1 positions, there are

m + n - p1 - 1 ≥ m - 1 - p1 + n - p2 - 1

Conversion result: p2 ≥ - 1

It can be proved that p1 is always enough to accommodate the inserted element, and nums1 element will not be overwritten

Array boundary:

nums1.length == m+n

nums2.length == n

m + n - p1 - 1 ≥ m - 1 - p1 + n - p2 - 1

Implementation code:

Idea 1: violent merger

# Train of thought I
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        nums1[m:] = nums2                   # The element after slicing to the m element is equal to the element of nums2
        nums1.sort()                        # Because it's just a merge, it still needs to be reordered

Idea 2: double pointer

# Train of thought II
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        sorted = []                                 # Create a temporary variable
        p1, p2 = 0, 0                               # Traverse from scratch
        while p1 < m or p2 < n:                     # Cycle condition
            if p1 == m:                             # When nums1 is completely traversed, only the elements of nums2 are not traversed
                sorted.append(nums2[p2])            # Because nums2 is ordered, you only need to constantly add nums2 elements
                p2 += 1
            elif p2 == n:                           # When nums2 is completely traversed, only the elements of nums1 are not traversed
                sorted.append(nums1[p1])            # Because nums1 is ordered, you only need to add the elements of nums1 continuously
                p1 += 1
            elif nums1[p1] < nums2[p2]:             # When comparing two array elements and nums2 current element is large
                sorted.append(nums1[p1])
                p1 += 1
            else:                                   # When comparing two array elements and nums1 current element is large
                sorted.append(nums2[p2])
                p2 += 1
        nums1[:] = sorted                           # Sorted array is the desired array. Just make nums1 equal to sorted

Idea 3: Official code

# Idea 3 Official code

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        p1, p2 = m - 1, n - 1                       # Let p1 and p2 be the last valid element of the two arrays
        tail = m + n - 1                            # Set tail as the last element of nums1
        while p1 >= 0 or p2 >= 0:                   # If the condition does not hold, the traversal is completed
            if p1 == -1:                            # When nums1 array is traversed completely
                nums1[tail] = nums2[p2]             # Just add the element of nums2
                p2 -= 1
            elif p2 == -1:                          # When nums2 array is traversed completely
                nums1[tail] = nums1[p1]             # Just add the element of nums1
                p1 -= 1
            elif nums1[p1] > nums2[p2]:             # When the nums1 element is larger than nums2
                nums1[tail] = nums1[p1]
                p1 -= 1
            else:                                   # When the nums2 element is larger than nums1
                nums1[tail] = nums2[p2]
                p2 -= 1
            tail -= 1                               # After triggering the condition, tail moves backward by one bit

If it is difficult to understand, you can gradually observe the code logic by watching the official commentary video or executing the following code

Python Tutor - Visualize Python, Java, JavaScript, C, C++, Ruby code execution

nums1 = [1,2,3,0,0,0]
nums2 = [2,5,6]
m = 3
n = 3

class Solution:
    def plusOne(self, nums1,nums2):
        p1, p2 = m - 1, n - 1
        tail = m + n - 1
        while p1 >= 0 or p2 >= 0:                   # If the condition does not hold, the traversal is completed
            if p1 == -1:                            # When nums1 array is traversed completely
                nums1[tail] = nums2[p2]             # Just add the element of nums2
                p2 -= 1
            elif p2 == -1:                          # When nums2 array is traversed completely
                nums1[tail] = nums1[p1]             # Just add the element of nums1
                p1 -= 1
            elif nums1[p1] > nums2[p2]:             # When the nums1 element is larger than nums2
                nums1[tail] = nums1[p1]
                p1 -= 1
            else:                                   # When the nums2 element is larger than nums1
                nums1[tail] = nums2[p2]
                p2 -= 1
            tail -= 1                               # After triggering the condition, tail moves backward by one bit
        return nums1

if __name__ == '__main__':
    s = Solution()
    S = s.plusOne(nums1,nums2)
    print(S)

Idea 3: simplify the cycle

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        p1, p2 = m - 1, n - 1
        tail = len(nums1) - 1
        while p2 >= 0:
            if p1 < 0 or nums1[p1] <= nums2[p2]:
                nums1[tail] = nums2[p2]
                p2 -= 1
            else:
                nums1[tail] = nums1[p1]
                p1 -= 1
            tail -= 1

Conclusion:

The second idea is forward double pointer traversal, in which the last num [:] = sorted rather than nums1 = sorted is because nums1 = sorted is a value assignment, which only changes the formal parameters and does not change the memory of the actual parameters

Train of thought 2 is train of thought 3. By using the sorted conditions and the initial length of nums1 is m + n, the parameters of temporary variables can be reduced and nums1 can be modified directly