Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities.

Hello everyone, I am quick-frozen fish 🐟, a front end of water system 💦, like colorful whistle 💐, continuous sand sculpture 🌲, I am a good brother of the next door Cold grass Whale, I just started to write an article. If you like my article, you can follow ➕ to like it, inject energy into me, and grow with me

Preface 🌧 ️

Algorithms are unfamiliar and familiar to the front-end people, and often we don’t value them as much as the back-end engineers do. But in fact, algorithms have an unshakable position for every programmer.

Because the development process is to convert the actual problem into the computer can recognize the instructions, that is, “data structure” said, “design the data structure, in the application of algorithms on the line”.

Of course, learning is also focused, as the front end we do not need to fully grasp the algorithm like back-end development, some of the more partial, not practical type and solution method, as long as a little understanding.

The title 🦀

88. Merge two ordered arrays

Difficulty is simple

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 1:

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

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0 Output: [1] Description: Combine [1] and []. The combined result is [1].Copy the code

Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1 Output: [1] Description: The arrays to be merged are [] and [1]. The combined result is [1]. Note that there are no elements in nums1 because m = 0. The only zeros left in NUMs1 are simply to ensure that the merge results can be safely stored in NUMs1.Copy the code

Tip:

  • nums1.length == m + n

  • nums2.length == n

  • 0 <= m, n <= 200

  • 1 <= m + n <= 200

  • -109 <= nums1[i], nums2[j] <= 109

** Can you design and implement an O(m + n) time complexity algorithm to solve this problem?

🌵

  • This problem is traversed from back to front
  • To prevent elements from being destroyed by traversing from front to back when changing in place
  • We have to go backwards!

How to solve the problem 🐂

  • Create three Pointers to
  • Nums1 has the end of a number
  • Nums2 has numeric ends
  • At the end of nums1
  • To iterate over

Source 🔥

/ * * *@param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    let i = m-1;
    let j=n-1;
    let k=m+n-1;
    while(i>=0||j>=0) {if(i<0){
            nums1[k--]=nums2[j--]
        }
        else if(j<0){
            nums1[k--]=nums1[i--]
        }
        else if(nums1[i]<nums2[j]){
            nums1[k--]=nums2[j--]
        }
         else if(nums1[i]>=nums2[j]){
            nums1[k--]=nums1[i--]
        }
    }
    return nums1
};
Copy the code

Time complexity :O(m+ N)

Space complexity :O(1)

Conclusion 🌞

So fish fish LeetCode algorithm chapter “LeetCode” 88- merge two ordered arrays ⚡️ is over, there is no shortcut to this algorithm, can only write more practice, more summary, the purpose of the article is actually very simple, is to urge myself to complete the algorithm practice and summary and output, dishes are not important, but love 🔥, I hope everyone can like my essay, and I also hope to know more like-minded friends through the article. If you also like to toss, welcome to add my friend, sand sculpture together, together progress.

Making 🤖 : sudongyu

Personal blog 👨💻: Frozen fish blog

Vx 👦 : sudongyuer

Write in the last

Guys, if you like my words, give 🐟🐟 a thumbs up 👍 or follow ➕ to support me the most.