88_Merge Sorted Array

[Easy][Array, Two Pointers]

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

• You may assume that nums1 has enough space (size that is greater or equal tom+n) to hold additional elements from nums2.

• The number of elements initialized in nums1 and nums2 are m and n respectively.

Example:

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

Output: [1,2,2,3,5,6]

Solution：

Idea:

• Fill nums1 from the end.

• Compare existing elements of two arrays from the end, the larger one move to the end.

Time Complexity: $O(m+n)$

Space Complexity: $O(1)$

def merge(nums1, m, nums2, n):
    """
    :type nums1: List[int]
    :type m: int
    :type nums2: List[int]
    :type n: int
    :rtype: void Do not return anything, modify nums1 in-place instead.
    """
    # two pointers for two arrays
    p1, p2, p = m-1, n-1, m+n-1
    while p1 >= 0 and p2 >= 0:
        if nums1[p1] >= nums2[p2]:
            nums1[p] = nums1[p1]
            p1 -= 1
        else:
            nums1[p] = nums2[p2]
            p2 -= 1
        p -= 1
    # if nums1 has entries left, they will be in the right place.
    # if nums2 has entries left, need to move to corresponding place in nums1
    while p2 >= 0:
        nums1[p] = nums2[p2]
        p2 -= 1
        p -= 1