# 合并有序数组

说明:nums1 和 nums2 是两个有序的数组,将 nums2 合并到 nums1 中并保持 nums1 中是有序的。

思路:可以使用 Java 自带的 arraycopy 方法,也可以使用多一个数组来作为中间比较的部分,然后来合并数组。

# ArrayCopy 方法

了解一下ArrayCopy方法

System.arrayCopy 的源代码声明 :

public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length)
   //     代码解释:
  //Object src : 原数组
   //int srcPos : 从元数据的起始位置开始
  //Object dest : 目标数组
  //int destPos : 目标数组的开始起始位置
  //int length  : 要 copy 的数组的长度

例子说明:

我们有一个数组数据 int [] array_1 = new byte; // 源数组

int[] array_2= new byte[5]; // 目标数组

我们使用 System.arraycopy 进行转换 (copy)
System.arrayCopy(array_1 ,0,array_2 ,0,5);
上面这段代码就是:创建一个一维空数组,数组的总长度为 12 位,然后将 array_1 源数组中 从 0 位 到 第 5 位之间的数值 copy 到 array_2 目标数组中,在目标数组的第 0 位开始放置.
那么这行代码的运行效果应该是 2,4,0,0,0,

定义方法

static void ArrayCopyMerge(int[] nums1,int x,int[] nums2,int y){
    // 利用自带的 ArrayCopy 方法进行合并
    System.arraycopy(nums2,0,nums1,x,y);
    // 使用快排对数组进行排序,保证他的有序性
    Arrays.sort(nums1);
}
// 主方法
    public static void main(String[] args) {
        int[] nums1={1,2,3,4,5,8,7,6,0,0,0,0,0,0,0};
        int[] nums2={10,11,12,113,14,15,18};
        ArrayCopyMerge(nums1,nums1.length,nums2,nums2.length);
        for(int i = 0 ; i<nums1.length;i++){
            System.out.print(nums1[i]+" ");
        }
    }
// 控制台输出
// 1 2 3 4 5 6 7 8 10 11 12 14 15 18 113

这里的数组可以是中间有一块值是需要填充的,只需要把 srcPosdestPoslength 设置清楚

这个方法的主要时间都在快排上,众所周知快排的时间复杂度是 O (n^2n2),当数组的大小很大的时候,就会耗上一段时间

# 使用空间换时间

使用多一个数组来进行对比,这样就不需要快排来重新排序

static void ReplaceArrayMerge(int[] nums1, int x, int[] nums2, int y) {
    // 定义一个和中间数组
    int[] nums1_copy = new int[x];
    // 将这个数组的的值设置成和 nums1 一样
    System.arraycopy(nums1, 0, nums1_copy, 0, x);
    //pointer 指针指向 nums1,pointer1 指向 nums1_copy,pointer2 指向 nums2
    int pointer = 0, pointer1 = 0, pointer2 = 0;
    // 判断数组值的大小并将值重新赋给 nums1
    //pointer < x 说明 nums1 后面等于 0 的值已经重新进入 nums1 了
    //pointer2 < y 说明 nums2 数组的值全部是比 nums [pointer1] 值要小
    while (pointer < x && pointer2 < y) {
        nums1[pointer++] = nums1_copy[pointer1] > nums2[pointer2] ? nums2[pointer2++] : nums1_copy[pointer1++];
    }
    // 当 nums2 数组的值全部是比 nums [pointer1] 值要小的时候,此时还有 x-(pointer1 + pointer2) 个数值没有拷贝
    if (pointer1 < x) {
        int temp = pointer1 + pointer2;
        System.arraycopy(nums1_copy, pointer1, nums1, temp, x - temp);
    }
    // 出现这种情况是因为 nums2 [pointer2] 的值比 nums1 最大的数值都要大,使用 nums2 还有值没有拷贝到 nums1 中
    if (pointer2 < y) {
        int temp = pointer1 + pointer2;
        System.arraycopy(nums2, pointer2, nums1, temp, y - pointer2);
    }
}

主方法:

public static void main(String[] args) {
    int[] nums1 = {1, 2, 3, 4, 50, 60, 70, 0, 0, 0, 0, 0, 0, 0};
    int[] nums2 = {10, 11, 12, 13, 14, 15, 18};
    ReplaceArrayMerge(nums1, nums1.length, nums2, nums2.length);
    for (int i = 0; i < nums1.length; i++) {
        System.out.print(nums1[i] + " ");
    }
}
// 控制台输出:
// 1 2 3 4 10 11 12 13 14 15 18 50 60 70

使用这个方法在时间上是要比上面的快排要快一点,但是这个方法又多占用了空间,同样当数组大的时候,空间开销就会变大

# 上面的改良

由于第二种方法是使用多一个数组从头开始比较,那我们也就可以从后面开始比较,从 nums1 和 nums2 有效数字开始比较,排除掉 nums1 后面的 0(因为是两个有序的数组合并,所以后面的 0 全部都是占位的)

static void BackArrayMerge(int[] nums1, int x, int[] nums2, int y) {
    //pointer 是 nums1 的最后的下标,pointer1 是 nums1 有效数字最后的下标值,pointer3 是 nums2 最后的下标
    int pointer = x - 1, pointer1 = x - y - 1, pointer2 = y - 1;
    while (pointer1 >= 0 && pointer2 >= 0) {
        nums1[pointer--] = nums1[pointer1] > nums2[pointer2] ? nums1[pointer1--] : nums2[pointer2--];
    }
    // 出现这种情况是因为 nums2 [pointer2] 的值要比 nums1 最小的值还要小,所以要将 num2 前面的拷贝的 nums1 的头部
    if (pointer2 >= 0) {
        System.arraycopy(nums2, 0, nums1, 0, ++pointer2);
    }
}
// 主方法
   public static void main(String[] args) {
        int[] nums1 = {3, 4, 10, 11, 50, 60, 70, 0, 0, 0, 0, 0, 0, 0};
        int[] nums2 = {1, 2, 12, 13, 14, 15, 18};
        BackArrayMerge(nums1, nums1.length, nums2, nums2.length);
        for (int i = 0; i < nums1.length; i++) {
            System.out.print(nums1[i] + " ");
        }
    }
// 控制台输出
// 1 2 3 4 10 11 12 13 14 15 18 50 60 70

有待更新…