1. The subject

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

2. Solution 1: sort directly after merging

var merge = function(nums1, m, nums2, n) { nums1.splice(m, nums1.length - m, ... nums2); nums1.sort((a, b) = > a - b);
};
Copy the code

  • Complexity analysis:

    • Time complexity: Different browsers have different implementations of sort. The average case is O((m+n)log(m+n)).

    • Space complexity: log(m + n)

3. Solution two: double pointer method

/ * * *@param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
  let result = []
  let nums1Index = nums2Index = 0

  while(nums1Index < m && nums2Index < n) {
    if(nums1[nums1Index] <= nums2[nums2Index]) {
      result[nums1Index + nums2Index] = nums1[nums1Index++]
    } else {
      result[nums1Index + nums2Index] = nums2[nums2Index++]
    }
  }

  while(nums1Index < m) {
    result[nums1Index + nums2Index] = nums1[nums1Index++]
  }

  while(nums2Index < n) {
    result[nums1Index + nums2Index] = nums2[nums2Index++]
  }
  
  const length = result.length
  for(let i = 0; i < length; i++) {
    nums1[i] = result[i]
  }
};
Copy the code
  • Complexity analysis:

    • Time complexity: ** O(m+n)** because at most only one num1 and num2 array is traversed

    • Space complexity: O(m+n) requires an intermediate array of length m+n

4. Solution three: Double-pointer optimization (reverse double-pointer)

/ * * *@param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {

  let nums1Index = m - 1
  let nums2Index = n - 1
  while(nums1Index >=0 && nums2Index >= 0) {
    if(nums1[nums1Index] >= nums2[nums2Index]) {
      nums1[nums1Index + nums2Index + 1] = nums1[nums1Index--]
    } else {
      nums1[nums1Index + nums2Index + 1] = nums2[nums2Index--]
    }
  }

  while(nums2Index >= 0) {
    nums1[nums2Index] = nums2[nums2Index--]
  }
};
Copy the code
  • Complexity analysis:

    • Time complexity: O(m+n) because at most only one num1 and num2 array is traversed

    • Space complexity: O(1) directly modifies the array nums1 in place, requiring no extra space.

5. To summarize

It looks like solution one is faster, but you have to look at it from a complexity perspective

  • Time complexity O((m+n)log(m+n)) space complexity log(m+n)
  • Solution 2: Time complexity O(m+n) space complexity O(m+n)
  • Solution 3: Time complexity O(m+n) space complexity O(1)

So solution three is better

Ps: But usually in the development of the amount of data will not affect the efficiency, I will use the first type, because it is too simple 😁