The title

You are given two non-descending arrays of integers, 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 in non-descending order.

Note: Finally, the merged array should not be returned by the function, but stored in the array nums1. To deal with this, nums1 has an initial length of m + n, where the first m elements represent the elements that should be combined and the last n elements are 0 and should be ignored. Nums2 has a length of n.

Example 1:

Input: nums1 =,2,3,0,0,0 [1], m = 3, nums2 = [6] 2, n = 3 output:,2,2,3,5,6 [1] : need to merge [1, 2, 3] and [6] 2. The combined result is [1,2,2,3,5,6], where the elements in italics and bold are nums1.Copy the code

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0 Output: [1] Description: Combine [1] and []. The combined result is [1].Copy the code

Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1 Output: [1] Description: The arrays to be merged are [] and [1]. The combined result is [1]. Note that there are no elements in nums1 because m = 0. The only zeros left in NUMs1 are simply to ensure that the merge results can be safely stored in NUMs1.Copy the code

Their thinking

  • nums1 、 nums2Ordered, if you takenums2Merge all intonums1, then the mergednums1Length ofm+n
  • We can go from the subscriptm+n-1Position fillnums1And compare thenums1[len1] 与 nums2[len2]To write the maximum valuenums1[len], i.e.,
    • nums1[len1]>=nums2[len2] ，nums1[len--] = nums1[len1--]Here,--The reason is that the subscript is automatically decreased by one after the write is successful
    • Otherwise,nums1[len--] = nums2[len2--]
  • Boundary conditions:
    • iflen1 < 0, i.e.,len2 >= 0At this time,nums1Has been rewritten,nums2It’s not done yet. It just needs to mergenums2The remaining elements (0… Len) writenums2Then, the merge is complete
    • iflen2 < 0At this time,nums2All have been merged intonums1, the merger is complete

code

var merge = function(nums1, m, nums2, n) {
  let len1 = m - 1,
      len2 = n - 1,
      len = m + n - 1
  while(len2 >= 0) {
      if(len1 < 0) {
          nums1[len--] = nums2[len2--]
          continue
      }
      nums1[len--] = nums1[len1] >= nums2[len2] ? nums1[len1--]: nums2[len2--]
  }
}
Copy the code