Topic describes

This is 88 on LeetCode. Merging two ordered arrays is easy.

Keyword: array 、、、、

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

Advanced: Can you design and implement a time complexity O(m + N) algorithm to solve this problem?

To highlight

  1. Both are ordered arrays.
  2. Nums1 has a length of m + n, that is, elements after m can store data at will. And the end result is just usenums1Can holdnums1 和 nums2The merged data.
  3. When two numbers are the same size,nums1Put the data in front,nums2The data is placed later.

Their thinking

If we were to iterate through nums1 and nums2 from front to back, we would have to overwrite nums1 elements, and we would have to create new memory to store data or a copy of Nums1, so we can change the way we think about it. We can start from the back and put the large first in array, You still end up merging two arrays perfectly. When two values are of the same size, the nums2 value is entered first.

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // Two Pointers to arrays
        int p1 = m - 1;
        int p2 = n - 1;
        // Finally store the pointer to the data
        int p = m + n - 1;
        int value;
        // continue as long as either nums1 or nums2 is not iterated
        while(p1 > -1 || p2 > -1) {
            if (p1 == -1) {
                // Array 1 is empty, insert array 2
                value = nums2[p2--];
            } else if (p2 == -1) {
                // Array 2 is empty, insert array 1
                value = nums1[p1--];
            } else if (nums1[p1] > nums2[p2]) {
                // If 1 is large, insert 1
                value = nums1[p1--];
            } else {
                // 2 is not less than 1, insert 2
                value = nums2[p2--];
            }
            // Record the data and move it one bit to the leftnums1[p--] = value; }}}Copy the code

reference

My Github repository has been set up synchronously, click access