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

Preface:

Motivational daily at least one problem, and write down the solution, dead knock algorithm, come on

The first day we talked about the sum of two numbers, which is an array type problem, and today we’re going to talk about array types

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.

Difficulty: Easy

Example 1:

Enter: nums1 = [1.2.3.0.0.0], m = 3, nums2 = [2.5.6], n = 3Output:1.2.2.3.5.6] Explanation: need to merge [1.2.3] and [2.5.6]. The combined result is [1.2.2.3.5.6], where the elements in italic bold are nums1.Copy the code

Subject address: leetcode-cn.com/problems/me…

Train of thought

First we should extract key words from the topic

  • 1. Non-descending order, that means order
  • 2. The merged array should not be returned by the function, but stored in the array nums1. So we’re going to manipulate nums1.
  • 3. There are three empty slots behind nums1, which are definitely useful. 😝

lenovo

We can relate to examples from our lives

We have two shelves of books in ascending order, now we want to put the second row of books on the first row of shelves, how can save more time and effort

  • 1. Method 1: We put the books in the second row directly behind the books in the first row, and then compare them one by one (sorting after merging, which is the most laborious).

Can we compare the books in the first row with the ones in the second row?

  • 2. Method 2: If the first book in the second row is smaller than the first book in the first row, we give the first place to the first book in the second row, put the first book in the first row for use in the third row, or move all the books in the first row back. This is what we found that this method is also not very labor-intensive (double pointer left contrast)
  • 3. Method 3: We compare the books in the first and second rows from the right side one by one. Then we find that when we extract key words from the questions, we find that

There are three empty Spaces behind nums1, so we don’t need to create the latest space, and we don’t need to move all the books backwards.

After ostentatious analysis, we find method three is the most convenient

The above comparison method is the two-pointer method

So when can we think about doing it with double Pointers?

  • 1. Dual Pointers are divided into left and right Pointers and fast and slow Pointers
  • 2. We can think of left and right Pointers whenever we encounter arrays and strings
  • 3. Just an arrayThe orderly“Immediately think of the left and right hands
  • 4. Encounter linked list problem we can think to the fast or slow pointer

Answer key

var merge = function (nums1, m, nums2, n) {

let length = m + n - 1;

let first = m - 1; // The first row of Pointers

let second = n - 1; // Second row of Pointers

// If a row of books is compared and the pointer becomes -1, then we don't need to compare the pointer to -1, because there are no books in -1

First =-1 and second=-1, length>-1, length>-1, length>-1, length>-1, length>-1, length>-1, length>-1

    while (first > -1 && second > -1) {

        if (nums1[first] > nums2[second]) {

            nums1[length] = nums1[first]; // the length of the book is given to the first row of books

            length--; // Then move the pit forward

            first--; // First move forward

        } else {

            nums1[length] = nums2[second]; // the length of the book is given to the second row of the book

            length--; // Then move the pit forward

            second--; // First move forward}}// If the above execution is complete, there may be some books left uncompared, so we directly give the first position of length to him

// If the books in the first row are not compared, we do not need to compare them, because we do not need to move those books, so we need to consider whether the books in the second row are compared

    while (second > -1) { nums1[length] = nums[second]; second--; length--; }};Copy the code

reference

  • LeetCode problem no. 88: Merge two ordered arrays