Power button brush the topic of merging two orderly array

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

题目

给你两个按 非递减顺序 排列的整数数组 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--];
             }
        }

复制

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