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

[B] [C] [D]

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

Description:

  • A.length == n + m

Their thinking

Since the input arrays A and B are both ordered arrays, we can ensure that the combined array is still ordered as long as we ensure that the elements in array B are inserted into the appropriate positions during the merge process. Here we define two Pointers, a and B, to the last element of array A and b. Each time a is moved forward to the first position where B points to an element less than or equal to a (if the original a points to an element less than or equal to b points to an element, no need to move), then the element after a is uniformly moved back one bit, and b points to the element in the vacant position. This ensures that each insertion in B is in the right place, and array A remains in order after insertion. We move the pointer to B forward and repeat the process until we have processed all the elements in array B, and we are done merging B into A.

The demo

Code implementation

Var merge = function (A, m, B, n) {var merge = function (A, m, B, n) { While (a [a] > b [b]) {// Initialize the pointer b to the last element of the array b = n-1 // process each element of the array B from the back forward while (b >= 0) {// Make a point of the first element that is less than or equal to b while (a [a] > b [b]) Move (a, a) move(a, a) // Move (b) to the empty position where the element is inserted a [a + 1] = b [b] // Move (b) forward to handle the remaining element b--} /* * Pass in the array and the specified subscript, * @param {number[]} arr * @param {number} ind * * @return {void} */ function move(arr, For (let I = arr. Length - 2; let I = arr. i > ind; i--) { arr[i + 1] = arr[i] } } }Copy the code

At this point we are done with Leetcode – interview question 10.01- merging sorted arrays

If you have any questions or suggestions, please leave a comment! 👏 🏻 👏 🏻 👏 🏻