力扣刷题之合并两个有序数组

力扣刷题之合并两个有序数组

题目

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

首先一种暴力的解法 我们可以直接将两个数组合并，然后直接排序 从数组的有效位的后边开始直接将num2的数组元素赋值去过，然后这样两者合并后在利用数据排序的方法一起排序。底层原理是一种快速排序。

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

复制

这样做的一个弊端就是，我们给出的两个数组都是有序数组，但是我们如果重新合并再排序的话，就又打乱了一次，没有利用上原来未合并数组的有序特点。

于是我们提出一种新的办法。如下，我们定义两个索引，其实你可以认为它是移动的指针，数组1，2分别是给出的nums1,nums2,然后我们定义一个临时数组。临时数组的大小等于num1

那么这样准备后怎么做呢？首先一号数组和二号数组两个指针指向的初始话都是数组头部。比较开始，如果一号指针指向数组的表头索引处的元素的值大于第二个的头部，那么我们将数组二头部的元素给到临时数组头部。否则就给数组一的，相等的话给哪个数组都可以。

给定后对应数组的指向指针后移，如下。相等的时候我们给定哪个都可以

你看这样就是一个排序的结果，最后我们将临时数组的元素值再重新赋值给num1.因为题目要求给到num1。

到了这一步的时候，我们的3也给了临时数组，这个时候后面的元素不是有效的了，所以我们就直接将num2剩余的元素给到临时数组

实现代码

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];
        }
}

复制

还有一种就是我们可以不用去做一个临时数组，因为num1的数组后面本来据预留出来了空间。比较的时候我们可以逆序去比较，也就是从两者的醉胡一个元素开始移动比较，元素大的放在num1后面，依次从后往前添加。

初始两者的指针都再尾部。然后开始比较。

然后按照这样的方法下去

到这里呢，如果nums1的元素较大的话，我们会让它后移。

然后小的会取代原来位置的元素，其实这样比划一番后，你会发现结束条件局势num2那里我们用的指针指向头部后，比较完后然后返回循环的时候，判断指针下一次移动是不是索引小于1，小于1就break；结束掉。

当然如果nums1的元素很多比较大的话，很可能就是它先遍历完，那么这样的话，我们就之直接将我们nums2的元素们依次给到nums11前面。这样也就是排好序了。

  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--];
             }
        }

复制

比较这三种做法呢，第一种比较耗时，因为存在一个打乱后后的再排序，后两种会使用类似指针的移动索引比较，没有打乱原本数组的有序，效率都非常高，但是第三种是没有使用临时数组，所以第三种的空间复杂度比较低，占用内存少。