First, understand the topic

88. Merge two ordered arrays

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:

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

This question is officially labeled easy, but I think it’s a bit of a medium difficulty…

Ii. Solution analysis

According to the above problem, let’s look at the idea of solving this problem. Details are as follows:

  • Define two Pointersp1 和 p2 ， p1To control arraysnums1The subscript,p2To control arraysnums2The subscript;
  • Define an arraysortedAnd fill it up0 ；
  • Fill the current valuecurThe four conditions are: ①p1A pointer is equal to themValue; 2.p2A pointer is equal to thenValue; 3.nums1[p1] < nums2[p2]When; ④ The rest.

Three, code implementation

Now we’re going to use JS to do this. The specific implementation code is as follows:

/ * * *@param {Array} nums1 
 * @param {Number} m 
 * @param {Array} nums2 
 * @param {Number} n 
 * @returns * /

var merge = function(nums1, m, nums2, n) {
    // 1. Define two Pointers p1 and p2, p1 controls m and p2 controls n
    let p1 = 0, p2 = 0;
    // 2. Initialize the sorted array and fill each element with zeros
    const sorted = new Array(m + n).fill(0);
    // 3. Define a cur that represents the current value
    let cur;
    // 4. Judgment condition: p1 is less than m or p2 is less than n
    while (p1 < m || p2 < n) {
        4.1 When p1 is equal to m, it indicates that P1 has reached the end. In this case, perform the +1 operation on P2
        if (p1 === m) {
            cur = nums2[p2++];
        } 
        // 4.2 When p2 is equal to n, p2 has reached the end of its path. In this case, perform the +1 operation on P1
        else if (p2 === n) {
            cur = nums1[p1++];
        } 
        // 4.3 If the value of nums1 corresponding to P1 is less than the value of nums2 corresponding to p2, the current value is equal to nums1[p1], and p1 is +1
        else if (nums1[p1] < nums2[p2]) {
            cur = nums1[p1++];
        } 
        In other cases, the current value is equal to nums[p2] and p2 +1
        else {
            cur = nums2[p2++];
        }
        5. Put them into the sorted array one by one
        sorted[p1 + p2 - 1] = cur;
    }
    // 6. Overlay the contents after nums1
    for (let i = 0; i ! = m + n; i++) { nums1[i] = sorted[i]; }// 7. Return the final array
    return sorted;
};
​
console.log(merge([1.2.3.0.0.0].3[2.5.6].3));
Copy the code

Merge two ordered arrays. Merge two ordered arrays.

We’ll see you next time at 👋👋👋