Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

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 👋👋👋