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
  • -10^9 <= nums1[i], nums2[i] <= 10^9

Second, train of thought analysis

In this problem, we use the double-pointer method to solve:

  • First we define two Pointers, each pointing to the end of two valid parts of the array:

  • Only the element to which the pointer points is compared at a time. Take the larger element and fill it from the end of nums1 to the front:

  • Consider emptying one of the arrays in advance:
    • If nums1 is traversed in advance, add nums2 in front of nums1.
    • If nums2 is traversed ahead of time, there is no need to do any additional operations.

AC code

/** * @param {number[]} nums1 * @param {number} m * @param {number[]} nums2 * @param {number} n * @return {void} Do not */ var merge = function(nums1, m, nums2, n) {// merge = function(nums1, m, nums2, n) { Let I = m-1, j = n-1, k = m + n-1 while(I >= 0 &&j >= 0) { If (nums1[I] >= nums2[j]) {nums1[k] = nums1[I] I -- k--} else {nums1[k] = nums2[j] j-- k--}} A special processing while (j > = 0) {nums1 [k] = nums2 [j], j, k}};Copy the code

Four,

  • When merged into NUMs1, it fills back to front to avoid the problem of overwriting values.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign