Three minutes a day, embark on the counter attack of the algorithm.

Previous collection

A daily LeetCode collection

Code warehouse

GitHub: https://github.com/meteor1993/LeetCode

Gitee: https://gitee.com/inwsy/LeetCode

Title: merging two ordered arrays

Title Source: https://leetcode-cn.com/problems/merge-sorted-array/

Here are two ordered integer arrays ， nums1 and nums2. Please merge nums2 into ， nums1 ， to make nums1 an ordered array.

explain:

The number of elements initializing nums1 and nums2 is m and n respectively.

You can assume that nums1 has enough space (the space size is greater than or equal to m + n) to store the elements in nums2.

Example:

input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

output: [1,2,2,3,5,6]

Problem solving scheme

This problem is not a difficult problem simply from the perspective of sorting. After all, two ordered arrays have been given in the problem. The simplest way is to cycle through the long array, then compare the sizes of the two array elements one by one, and put them into a new array.

The difficulty of this problem is that we need to sort the two arrays in nums1 array. This is a little pit, which is equivalent to merging nums2 into nums1 and merging them orderly.

This bend is a little difficult to get around. Although the title says that the final result should be in nums1, it doesn't say that we are not allowed to create a third array. I can create a new array, copy nums1 into the new array, and then sort in nums1. Isn't that ok.

Next is the code time, which is very simple. Two pointers are defined, one is copy_ The pointer of nums1 and the pointer of nums2 complete the whole sorting work by moving these two pointers.

// From front to back
public void merge(int[] nums1, int m, int[] nums2, int n) {
    int[] copy_nums1 = new int[m];
    System.arraycopy(nums1, 0, copy_nums1, 0, m);

    // copy_ Pointer to nums1
    int n1 = 0;
    // Pointer to nums2
    int n2 = 0;
    // Pointer to nums1
    int n0 = 0;

    while ((n1 < m) && (n2 < n)) {
        nums1[n0++] = copy_nums1[n1] < nums2[n2] ? copy_nums1[n1++] : nums2[n2++];
    }

    if (n1 < m) {
        System.arraycopy(copy_nums1, n1, nums1, n1 + n2, m + n - n1 - n2);
    }
    if (n2 < n) {
        System.arraycopy(nums2, n2, nums1, n1 + n2, m + n - n1 - n2);
    }
}

Although the above scheme can solve the problem, it is not very good, that is, a new array is created, which takes up more space of an array. Since the length of nums1 is enough, it is difficult for us to sort from small to large. What if it is from large to small?

The idea is basically one idea. Define two pointers, and then put the elements into nums1 in reverse order.

// From back to front
public void merge_1(int[] nums1, int m, int[] nums2, int n) {
    // nums1 has a tail pointer to the data
    int n1 = m - 1;
    // Tail pointer of nums2
    int n2 = n - 1;
    // nums1 final tail pointer
    int n0 = m + n - 1;

    while ((n1 >= 0) && (n2 >= 0)) {
        nums1[n0--] = nums1[n1] < nums2[n2] ? nums2[n2--] : nums1[n1--];
    }

    System.arraycopy(nums2, 0, nums1, 0, n2 + 1);
}

Today, these two questions are not difficult. After basically figuring out the scheme, you can write code and practice your hand.