5.合并两个有序数组

文章目录

题目简介
题目解答
- 解法一：合并后排序
- 解法二：双指针排序
题目链接

大家好，我是晓星航。今天为大家带来的是合并两个有序数组相关的讲解！😀

题目简介

在这里插入图片描述

题目解答

解法一：合并后排序

假设我们要合并下图这两个数组：
在这里插入图片描述
我们要将他们合并成一个数组并排序成有序的状态。
第一步：将数组2合并到数组一中：

第二步：将合并完成后的数组进行排序：

代码：

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        System.arraycopy(nums2,0,nums1,m,n);
        Arrays.sort(nums1);
    }
}

第三行调用的方法含义是从nums2这个数组的第0个元素位置开始拷贝到nums1从第m个元素开始，一共拷贝n个元素。
第四行代码的含义是通过调用Arrays的sort方法来对nums1这个数组进行排序

空间复杂度以及时间复杂度：
在这里插入图片描述

解法二：双指针排序

假设我们要合并下图的两个数组：
在这里插入图片描述
第一步：首先对数组1进行一个拷贝
双指针
第二步：对拷贝后的数组1和数组2进行遍历，在遍历时对两个指针此时拿到的值进行比较，并将较小的值放入原数组1中，然后指向较小值的指针++，继续比较

在这里插入图片描述

代码：

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] nums1_copy = new int[m];
        System.arraycopy(nums1,0,nums1_copy,0,m);

        int p1 = 0;
        int p2 = 0;

        int p = 0;
        while ((p1 < m) && (p2 < n)) {
           nums1[p++] = (nums1_copy[p1] < nums2[p2]) ? nums1_copy[p1++] : nums2[p2++];
        }
           if (p1 < m) {
            System.arraycopy(nums1_copy,p1,nums1,p1+p2,m+n-p1-p2);
           }
           if (p2 < n) {
            System.arraycopy(nums2,p2,nums1,p1+p2,m+n-p1-p2);
           }
    }
}

代码解析：
拷贝数组1并将拷贝好的新数组命名为nums1_copy。
在这里插入图片描述
设置指针p,p1,p2分别指向数组nums1,nums1_copy,nums2的头元素

比较指针p1和p2指向的数字，将较小的数组存入nums1后，指针后移，直至所有数字比较完毕

因为比较的条件是 p1<m和p2<n 他们的和运算，因此只要有一个不满足while循环就会跳出，此时一个指针已经全部走完，意味着另一个指针指向的数组全部都大于走完的那个指针的数组的所有元素，即直接将没走完的指针后面的元素全部拷贝到数组nums1后接上即可完成题目要求。
在这里插入图片描述
时间复杂度与空间复杂度：