“This is the 12th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

The title

Given two sorted arrays A and B, where the end of A has enough buffer space to hold B. Write A method that merges B into A and sorts.

Initialize A and B with m and N elements, respectively.

Example:

Input: A =,2,3,0,0,0 [1], m = 3 B = [6] 2, n = 3 output:,2,2,3,5,6 [1]Copy the code

Method a

Violent solution.

Train of thought

Just put all the elements of B into A, and then sort them.

Just to illustrate the idea, we’ll just use the insert method splice and the sort method that comes with the js array.

code

/ * * *@param {number[]} A
 * @param {number} m
 * @param {number[]} B
 * @param {number} n
 * @return {void} Do not return anything, modify A in-place instead.
 */
var merge = function(A, m, B, n) { A.splice(m, A.length - m, ... B); A.sort((a, b) = > a - b);
};
Copy the code

Method 2

Three pointer.

Train of thought

  1. Define A pointer right to the end of array A to specify where to insert the element.
  2. Define an rightA pointer to the last element of the ARRAY A.
  3. Define a rightB pointing to the last element of the B array.
  4. Traverse group A, starting from position rightA
    • Compare the size of A[rightA] and B[rightB]
    • If A[rightA] is rightA, set A[rightA] to A[right]
      • Then move rightA forward one space and move right forward one space
    • If B[rightB] is larger or equal, assign B[rightB] to A[right]
      • Then move rightB forward one space, and move right forward one space
  5. The traversal ends if neither rightA nor rightB is less than 0, and stops if either of them is less than 0
  6. And then we look to see if B has any value, that is, rightB is less than 0, and if it’s not less than 0, we iterate, we put all the rest of the values in B in front of A

So the whole idea is that we borrowed the merge sort idea from merge sort, but we’re going to merge from back to front, and we’re going to do it on an array.

Compare two ordered arrays, from the back to the front, and take whoever has the largest number.

The following code

/ * * *@param {number[]} A
 * @param {number} m
 * @param {number[]} B
 * @param {number} n
 * @return {void} Do not return anything, modify A in-place instead.
 */
var merge = function(A, m, B, n) {
    let right = m+n-1;
    let rightA = m-1;
    let rightB = n-1;

    while(rightA>=0&&rightB>=0) {if(A[rightA] > B[rightB]){
            A[right] = A[rightA];
            right--;
            rightA--;
        }else{ A[right] = B[rightB]; right--; rightB--; }}if(rightB>=0) {while(right>=0){
            A[right] = B[rightB];
            right--;
            rightB--
        }
    }
    return A
};
Copy the code

Complexity analysis

Time complexity: O(m+n), which requires traversing all elements of A and B to m+n in total

Space complexity: O(1). You do not need to apply for additional space to store data.