This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

1. Title Description

Merges two ordered arrays

Merge nums2 into nums1 to make nums1 an ordered array.

Initialize nums1 and nums2 to m and n, respectively. You can assume that nums1 has a space size equal to m + n so that it has enough space to hold elements from Nums2.

Example 1:

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

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0

Second, train of thought analysis

Conventional resolution

  • I’m sure the first thing that comes to mind is to merge two arrays and sort the whole array, and I have to say that’s the fastest way to do it because we have a threaded API to do it directly. A few lines of code will solve the problem
  • The first half of num1 is ordered, and the second half is reserved for storing num2 arrays.
  • Let’s merge two arrays without touching any third party variables. But we don’t use third parties when we merge

  • We didn’t introduce third party variables all along. This is really the fastest and easiest way to do it

Double pointer

  • Double-pointer means defining two Pointers (variable indexes) to two arrays, treating the two arrays as two queues each time removing smaller values from the two queues and stuffing them into a third array. And finally the third array is the merged array that we sorted

  • We don’t want to use third-party variables to do this. So can we use a double pointer to merge without using a third array?
  • The answer is yes. Because they tell us that num1 is the length of the merged array. The obvious reason is to output num1 as a merged array.
  • We can work backwards from the num1 array and fill the end of num1 with the largest number in the set, then fill the second to last position with the next largest number, and then fill the num1 array with all of them.

  • The extreme case is that num2 fills exactly the back half of NUM1, so we don’t need to move the first half of num1.

  • As long as num2 is not fully filled in the second half, the first half of num1 must have the maximum value moved. The place where the movement takes place must be at the end of the first half, and num2 has a chance to participate.
  • So no matter what happens, no element in the num1 array will be occupied, right

AC code

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int p1 = m - 1;
    int p2 = n - 1;
    for (int i = nums1.length - 1; i >= 0; i--) {
        int num1=Integer.MIN_VALUE, num2 = Integer.MIN_VALUE;
        if (p1 >= 0) {
            num1 = nums1[p1];
        }
        if (p2 >= 0) {
            num2 = nums2[p2];
        }
        if (num1 > num2) {
            p1--;
            nums1[i] = num1;
        } else{ p2--; nums1[i] = num2; }}}Copy the code
  • The idea is to start iterating over num1, each time using a double pointer to get the maximum value from the end of the array into NUM1.

Four,

  • I’m going to merge them all at first, and then sort them, which is pretty straightforward and pretty crude. They don’t take into account the properties of arrays that they mean
  • Then there is the double pointer merge, with the disadvantage of using a third variable.
  • For a change of thought, we start filling the data with a double pointer in reverse order to completely solve the problem of the third variable

Like + comment