Combining two ordered arrays

题目

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目.
请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列.
注意：最终,合并后数组不应由函数返回,而是存储在数组 nums1 中.为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略.nums2 的长度为 n .

The first is a violent solution
We can merge the two arrays directly,然后直接排序
Start directly after the significant bit of the arraynum2The array element assignment of ,Then, after the two are merged, they are sorted together using the data sorting method.The underlying principle is a quick sort.

 for (int i = 0; i < nums2.length; i++) {
    
            nums1[m++]=nums2[i];
        }         
        Arrays.sort(nums1);

One disadvantage of doing this is that,Both arrays we are given are sorted arrays,But if we re-merge and re-sort,Disrupted again,Does not take advantage of the ordered nature of the original unmerged array.

So we propose a new approach.如下,We define two indexes,Actually you can think of it as a moving pointer,数组1,2are given respectivelynums1,nums2,Then we define a temporary array.The size of the temporary array is equal to num1

So what do you do when you are ready？First of all, the initial words pointed to by the two pointers of the first array and the second array are the head of the array.比较开始,If the first pointer points to the value of the element at the head index of the array is greater than the second head,Then we give the elements of the second head of the array to the head of the temporary array.Otherwise, it is given to array one,It can be given to any array if it is equal.

Moves the pointer to the corresponding array backwards when given,如下.When equal, we can give either one

You see this is a sorted result,Finally, we reassign the element values ​​of the temporary array to num1.Because the title requires itnum1.

到了这一步的时候,我们的3Temporary array is also given,At this time, the following elements are not valid,所以我们就直接将num2The remaining elements are given to a temporary array

实现代码

class Solution {
    
    public void merge(int[] nums1, int m, int[] nums2, int n) {
    
     int nums3[] = new int[m+n];
     for (int i = 0; i < nums3.length; i++) {
    

            if(pre01>=m)
            {
    
               nums3[i]= nums2[pre02++];
            }
            else if (pre02>=n)
            {
    
               nums3[i]= nums1[pre01++];
            }
            else if (nums1[pre01]>=nums2[pre02])
            {
    
                nums3[i]=nums2[pre02++];
            }else if (nums1[pre01]<nums2[pre02])
            {
    
                nums3[i]=nums1[pre01++];
            }

        }
        for (int i = 0; i < nums1.length; i++) {
    
            nums1[i]=nums3[i];
        }
}

Another is that we don't have to do a temporary array,因为num1The back of the array was originally reserved for space.When comparing, we can compare in reverse order,That is to say, the comparison starts from the drunken element of the two,Elements are placed largenum1后面,Add in order from back to front.

Initially both pointers are tailed.然后开始比较.

Then go on like this

到这里呢,如果nums1If the element is larger,We'll move it back.


Then the smaller one will replace the element in its original position,In fact, after a lot of comparisons,You will find the end condition situationnum2There we use the pointer to point to the back of the head,When the comparison is done and then return to the loop,Determine whether the next move of the pointer is less than the index1,小于1就break;结束掉.

当然如果nums1A lot of elements are relatively large,It is likely that it has finished traversing first,那么这样的话,We'll take it straight to usnums2The elements are given in ordernums11前面.That's how it's sorted.

  int nums3[] = new int[m+n];

// for (int i = 0; i < nums2.length; i++) {
    
// nums1[m++]=nums2[i];
// }
// Arrays.sort(nums1);
// for (int i : nums1) {
    
// System.out.println(i);
// }
        int pre01 =m-1,pre02 =n-1;
        for (int i =m+n-1; i >=0; i--) {
    
             if (pre01<0)
             {
    
                 nums1[i]=nums2[pre02--];
             }
             else if (pre02<0)
             {
    
                 break;
             }else if (nums1[pre01]>nums2[pre02])
             {
    
                 nums1[i]= nums1[pre01--];
             }
             else{
    
                 nums1[i]= nums2[pre02--];
             }
        }

Compare these three approaches,The first is more time-consuming,Because there is a shuffled reordering,The latter two use pointer-like move index comparisons,The order of the original array is not disrupted,效率都非常高,But the third is not using a temporary array,Therefore, the space complexity of the third type is relatively low,占用内存少.