This article is participating in the nuggets team number online activity, click to see the dachang spring recruiting positions

88. Difficulty of merging two ordered arrays: Easy

1. Title Description

Merge nums2 into nums1 to make nums1 an ordered array. Initialize nums1 and nums2 to m and n, respectively. You can assume that nums1 has a space size equal to m + n so that it has enough space to hold elements from Nums2. Example 1:

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

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0Copy the code

Tip:

  • nums1.length == m + n
  • nums2.length == n
  • 0 <= m, n <= 200
  • 1 <= m + n <= 200
  • -109 <= nums1[i], nums2[i] <= 109

Second, train of thought analysis

Start at 0 and find the right number for each position. Use two Pointers to point to num1,num2 is currently traversed to the position, the comparison results in a smaller number, the number of Pointers forward one.

AC code

    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) - >None:
        """ Do not return anything, modify nums1 in-place instead. """
        p1 = m-1
        p2 = n-1
        index = n+m-1
        while index >= 0:
            if p1 >= 0 and (p2 < 0 or nums1[p1] > nums2[p2]):
                nums1[index] = nums1[p1]
                p1-=1
                index-=1
            else:
                nums1[index] = nums2[p2]
                p2-=1
                index-=1
Copy the code

Four,

Problems like this, which require moving in place, tend to be clearer from the idea of finding the right number for each subscript.

If you feel good, give me a thumbs-up 💐