“This is the 19th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”

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.

Example 2:

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

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.

 

Tip:

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

 

Advanced: Can you design and implement a time complexity O(m + N) algorithm to solve this problem?

Their thinking

Method 1: Use array properties

/ * * *@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) {
    return nums1.splice(0, m).concat(nums2.splice(0, n)).sort();
};
Copy the code

Here’s what I assumed when I saw the problem, and I printed it on the console as follows:

But I handed in the code and I didn’t get through the first use case. A closer look shows that the merged array should not be returned by the function, but stored in the array nums1. So here’s the solution

Method two: sort after merge directly

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

• Time complexity: O((m+n)log(m+n)).

  The length of the sorting sequence is M + N, and the time complexity of quicksort is O((m+n)log(m+n)) on average.

• Space complexity: O(log(m+n)).

  The length of the sorting sequence is M + N, and the space complexity of quicksort can be applied. The average case is O(log(m+n)).

Method three: double pointer

var merge = function(nums1, m, nums2, n) {
    let p1 = 0, p2 = 0;
    const sorted = new Array(m + n).fill(0);
    var cur;
    while (p1 < m || p2 < n) {
        if (p1 === m) {
            cur = nums2[p2++];
        } else if (p2 === n) {
            cur = nums1[p1++];
        } else if (nums1[p1] < nums2[p2]) {
            cur = nums1[p1++];
        } else {
            cur = nums2[p2++];
        }
        sorted[p1 + p2 - 1] = cur;
    }
    for (let i = 0; i != m + n; ++i) {
        nums1[i] = sorted[i];
    }
};
Copy the code

• Time complexity: O(m+ N).

  Pointer movement is monotonically increasing, at most m+ N times, so the time complexity is O(m+ N).

• Space complexity: O(m+ N).

  We need to create a sorted intermediate array of length m+n.

conclusion

This is Xiaokui 🌻, as long as you turn your heart toward the sun, you will have warmth ~

Let’s overcome the algorithm together!!