三种方法可合并两个有序数组

合并两个有序数组要怎么做？星辉小编来为大家举例说明。

我们先来看下题目要求：

给你两个有序整数数组 nums1 和 nums2，请你将 nums2合并到 nums1 中，使 nums1 成为一个有序数组。

说明：

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。

你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。

示例：

输入：

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

输出：

[1,2,2,3,5,6]

看到这个题目第一眼，你是不是也想到了直接把两个数组放在同一个数组里边，然后调用Arrays.sort() 然后就直接得到了结果呢，这样是可以的 但是浪费了题目中的 原数组也是有序的这个条件，且这样做的复杂度很高，为什么呢?

nums2数组拷贝到nums1数组，因为数组在物理内存中是连续的存储单元，合并数组时，本身并不会耗费很多的时间和空间，但是sort方法的底层是一种快速排序的方法，时间复杂度是O(nlog n)，因为两个数组本身就是有序的了，我们可以利用这个条件，在原数组遍历一遍的时候直接排序就好了，所以双指针，他来了!

public void merge(int[] nums1, int m, int[] nums2, int n) {
        int k = m + n - 1 ; //两个数组合在一起 最后那个数的下标
        int i = m - 1 ; // nums1 的最后一个数的下标
        int j = n - 1 ;// nums2 的最后一个数的下标
        while(i>=0 && j>=0) {  //从后往前遍历 直到最前边的数字都遍历完
            if(nums1[i] < nums2[j]){    //当nums1的最后一个数字小于nums2的最后一个数字
            nums1[k--] = nums2[j--] ;//这说明nums2最后一个数字是合并之后数组中值最大的后头的位置
            }else{  //否则放在远处不动 继续向下遍历
                nums1[k--] = nums1[i--] ;
            }
        }
        while(j>=0) nums1[k--]= nums2[j--] ;  //当nums1已经排序完之后 但是nums2还有数据
    }

写完之后，我们来测试一下;