88.合并两个有序数组

wuchangjian2021-11-05 13:42:50编程学习

题目描述:两个按非递减顺序排列的整数数组 nums1 nums2,另有两个整数 mn ,分别表示 nums1nums2 中的元素数目。

示例1:

输入:nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3
输出:[1, 2, 2, 3, 5, 6]
解释:需要合并 [1, 2, 3] 和 [2, 5, 6] 。

示例2:

输入:nums1 = [1], m = 1, nums2 = [], n = 0
输出:[1]
解释:需要合并 [1] 和 [] 。

 示例3:

输入:nums1 = [0], m = 0, nums2 = [1], n = 1
输出:[1]
解释:需要合并的数组是 [] 和 [1] 。

题目分析:通过观察题目我们发现 m 表示的是 nums1 数组中非零元素的数量,也就是待合并元素的数量,n 表示的是 nums2 数组中的元素数量,nums2 中的元素全部是待合并元素。m 和 n 之间的关系是:m + n = nums1.length。既然有此关系,那么这个就是此题的入口。基本方法是:用 m 去倒序循环 nums1 中待合并的元素,用 n 去倒序循环 nums2 中待合并的元素,两者进行比较,较大者设置为 nums1[m + n - 1] 的元素,然后根据实际情况选择给 m 或者 n 自减。考虑到这层循环处理之后数组中可能会有元素并没有参与比较,所以需要在循环外面处理未参与比较的元素,直接复制到 nums1 中即可。

以 nums1[] = {1, 2, 3, 0, 0, 0},nums2 = {2, 5, 6} 为例来看具体的处理过程:

一、循环之前准备工作:nums1[] = {1, 2, 3, 0, 0, 0},nums2 = {2, 5, 6}, m = 3,n = 3,使用 i 去循环 nums1 中的所有元素,倒序循环,因为下标从 0 开始,所以循环开始前 m = 2,n = 2,i = m + n - 1,循环条件是 m >= 0 && n >= 0。

二、循环开始:比较 nums2[n] 与 nums1[m] 的大小,较大者为 nums1[i] 赋值,之后 i--,并且较大者的循环变量自减,即:

if (nums2[n] >= nums1[m]) {
    nums1[i--] = nums2[n--];
} else {
    nums1[i--] = nums1[m--];
}

第一次循环:m = 2,n = 2,i = 5,满足循环条件,进入循环,nums2[n] = 6 >= nums1[m] = 3,此时,给 nums1[i] 赋值,nums1[5] = 6,然后 i--, n--

第二次循环:m = 2,n = 1,i = 4,满足循环条件,进入循环,nums2[n] = 5 >= nums1[m] = 3,此时,给 nums1[i] 赋值,nums1[4] = 5,然后 i--, n--

第三次循环:m = 2,n = 0,i = 3,满足循环条件,进入循环,nums2[n] = 3 >= nums1[m] = 3,此时,给 nums1[i] 赋值,nums1[3] = 3,然后 i--, n--

第四次循环:m = 2,n = -1,i = 2,不满足循环条件,退出循环

三、循环之后:此时 nums2[] 中元素已经比较完毕,nums1[] 中元素还未比较完毕,所以直接在循环外边对 nums1[] 中剩余元素进行处理即可。

那么,完整的代码就为:

public class Merge {

    public static void merge(int[] nums1, int m, int[] nums2, int n) {

        // i 用来循环 nums1[] 中所有的元素
        // m 用来循环 nums1[] 中非零元素
        // n 用来循环 nums2[] 中的元素
        int i = m + n - 1;
        m--;
        n--;
        // nums1[] 中的非零元素与 nums2[] 中的元素倒序进行比较
        // 当 nums2[n] 大于等于 nums1[m] 时,设置 nums1[i] 为两者中较大的元素,之后对循环变量 i、m、n 进行自减
        while (m >= 0 && n >= 0) {
            if (nums2[n] >= nums1[m]) {
                nums1[i--] = nums2[n--];
            } else {
                nums1[i--] = nums1[m--];
            }
        }
        // 处理 nums1[] 中剩余元素
        for (; m >= 0; m--, i--) {
            nums1[i] = nums1[m];
        }
        // 处理 nums2[] 中剩余元素
        for (; n >= 0; n--, i--) {
            nums1[i] = nums2[n];
        }
    }

    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        int[] nums1 = {4, 5, 6, 0, 0, 0};
        int[] nums2 = {1, 2, 3};
        int m = 3;
        int n = 3;
        merge(nums1, m, nums2, n);
        // 打印输出
        for (int x = 0; x < nums1.length; x++) {
            System.out.print(nums1[x] + "  ");
        }
        System.out.println();
        long endTime = System.currentTimeMillis();
        System.out.println("程序运行时间:" + (endTime - startTime) + "ms");
    }


}

这是最容易被想到的方法,除此之外还可以利用 sort 方法来进行排序,从而得到最终的结果。代码只有两行:

public class Merge {

    public static void merge2(int[] nums1, int m, int[] nums2, int n) {
        // 从 nums2 中下标为 0 的位置取出 n 个元素,放到 nums1 中从下标 m 开始的位置
        System.arraycopy(nums2, 0, nums1, m, n);
        // 排序
        Arrays.sort(nums1, 0, m + n);
    }

    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        int[] nums1 = {4, 5, 6, 0, 0, 0};
        int[] nums2 = {1, 2, 3};
        int m = 3;
        int n = 3;
        merge2(nums1, m, nums2, n);
        // 打印输出
        for (int x = 0; x < nums1.length; x++) {
            System.out.print(nums1[x] + "  ");
        }
        System.out.println();
        long endTime = System.currentTimeMillis();
        System.out.println("程序运行时间:" + (endTime - startTime) + "ms");
    }


}

相关文章

分享一些重要文章链接

近期看到一些不错的文章,记录 https://www.smiletoyo...

C语言概述(三)-- 宏定义、指针、结构体

宏定义指针结构体 1、宏定义      #define      每个参数加上括号&#x...

AtomicReference与AtomicReferenceFieldUpdater的使用

前言: 关于JDK提供的原子类,我们之前经常使用的就是基础...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。