Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities

1. Title Description

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.

Sample:

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.

2. How to solve the problem

First look at the requirements:

  1. nums1The initial array is not all nums1 values, but isnums2The elements preserve space
  2. A. nums1 b. nums2 C. nums1 D. nums2
  3. No value is returned in this case, and the final result is retained in nums1

P1 points to the MTH element of nums1, p2 points to the NTH element of nums2, and then moves the pointer to the end of nums1. Compare, place the value at the end of nums1, and move the pointer… This does not create the problem of overwriting values.

But there is a special case to consider: what if nums1 has no real elements? If we compare the values of two arrays based on Pointers, nums1[m-1] will not get the value because m is 0. In this case, we can set a separate conditional judgment, when m===0, take the value of nums2 into nums1. What if nums2 has no real elements? If nums2[n-1] is not available, what should we do?

AC code

var merge = function(nums1, m, nums2, n) {
    // Double pointer method
    // if (m === 0 || n === 0) {
    // // has no second argument and defaults to the end
    // nums1 = (m === 0) ? nums1.concat(nums2).slice(1) : nums1.concat(nums2)
    // }
    // Initialize two Pointers
    let p1 = m - 1
    let p2 = n - 1
    // start at the last position of nums1
    for (let i = m + n - 1; i >= 0; i--) {
        if(p1===-1) {// Put the corresponding nums2 values into nums1 without comparison
             nums1[i]=nums2[p2]
             p2--
        }
        else if(p2===-1) {// Select the corresponding nums1 value from nums1.
            nums1[i]=nums1[p1]
            p1--
        }
        else if (nums1[p1] >= nums2[p2]) {
            nums1[i] = nums1[p1]
            p1--
        } else if (nums1[p1] < nums2[p2]) {
            nums1[i] = nums2[p2]
            p2--
        }
    }
};
Copy the code

Four,

This problem is not difficult in general, need careful, serious.