合并两个有序数组

WangScaler: 一个用心创作的作者。

声明：才疏学浅，如有错误，恳请指正。

题目

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

初步分析

非递减顺序排列的数组，那么也就是递增的顺序数组，我们合并的话，只需要把新数组的按顺序插入到这个数组中，唯一的麻烦就是数组不像链表，数组是连续的，你要插入一个元素，那么必须将后边的所有元素后移。我们如果不后移，那么后边的元素就会被覆盖。我们要解决被覆盖的问题，最简单直接的方法就是复制一个原有的数组出来，既然返回的是原有的数组，我们比较新赋值的数组和第二个数组，将原有的第一个数组赋值。而且数组是引用类型，我们不能直接赋值，而是只能复制数据出来。

继续分析

public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int newNum[]= Arrays.copyOfRange(nums1,0,m);
        int i = 0;
        int j = 0;
        int num =0;
        while (i<m&&j<n){
            if(newNum[i]>nums2[j]){
                nums1[num] = nums2[j];
                j++;
            }
            else{
                nums1[num]= newNum[i];
                i++;
            }
​
            num++;
        }
        while (i<m && n!=0){
                nums1[num] = newNum[i];
                i++;
                num++;
        }
        while (j<n){
            nums1[num] = nums2[j];
            j++;
            num++;
        }
    }

此时，我们只需要遍历一遍两个数组即可实现目的，时间复杂度O(m+n)。但是我们引入了一个新的数组，空间复杂度是O(m)。那么有没有办法，再降低点空间复杂度呢？我们引入数组的目的就是防止第一个数组中后边的元素被第二个数组所覆盖，要想降低空间复杂度，问题还是在于这个数据的问题。

我们的惯性思维是从前往后，如果从后往前呢？我们知道我们第一个数组前边是有效数字，后边是无效可覆盖的数字，我们从后往前覆盖呢？

覆盖后的情况无非三种情况

• 第一个数组不变
• 第一个数组和第二个数组交叉
• 第一个数组在后边

我们采取从后往前遍历好像对原有两个数组的比较赋值都没有影响。

答案

public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int num = m + n - 1;
        while (num >= 0) {
            if (i >= 0 && j >= 0 && nums1[i] > nums2[j]) {
                nums1[num--] = nums1[i--];
            } else if (i >= 0 && j >= 0 && nums1[i] <= nums2[j]) {
                nums1[num--] = nums2[j--];
            } else if (i >= 0 && j < 0) {
                nums1[num--] = nums1[i--];
            } else {
                nums1[num--] = nums2[j--];
            }
        }
    }

• 第一个判断条件是第一个数组和第二个数组的数据比较大小，数组一大，放在数据的后边数组一下标往前移动。
• 第二个判断条件是第一个数组和第二个数组的数据比较大小，数组二大，放在数据的后边数组二下标往前移动。
• 第三个判断条件是第二个数组遍历完了，只剩下第一个数组，那么就把数组一的数据依次放进去即可。
• 第三个判断条件是第一个数组遍历完了，只剩下第二个数组，那么就把数组二的数据依次放进去即可。

我们看到第一个条件和第三个条件是一样的，第二个和第四个是一样的，其实我们可以简单的进行修改。

if (i >= 0 && (j >= 0 && nums1[i] > nums2[j]||j<0)) {
                nums1[num--] = nums1[i--];
            } else {
                nums1[num--] = nums2[j--];
            }

这样虽然不影响结果，但是不便于大家理解，代码的可读性稍微差点。

复杂度

• 时间复杂度: O(m+n)，分别遍历两个数组，所以时间复杂度为O(m+n)。
• 空间复杂度：O(1),我们将数组取代为三个指针，分别指向第一个、第二个数组的遍历位置，以及第一个数组的插入位置。

总结

一说到排序，往往大家习惯性的从头到尾进行处理，这种固化思维往往会影响我们对问题的处理。所以要多思考，换个方向进行思考，或许解决问题的方法更简单，所以生活中换位思考，也是一种难能可贵的品格。

都来了，点个赞再走呗！

关注WangScaler，祝你升职、加薪、不提桶！