[数据结构与算法]力扣打卡之合并两个有序数组

题目描述

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

初始化nums1和nums2的元素数量分别为m和n。假设nums1的空间大小等于m+ n,这样它就有足够的空间保存来自nums2的元素。

解题思路

①使用java底层提供的API ----? arraycopy

②使用双指针

可以使用双指针的方式进行从左到右的遍历，使用一个新的数组来存放原来的num数组，然后比较两个数组中元素的大小，将小的元素放在num1的第一位，以此类推！

最后我们就可以将元素排好序放到num1数组中了！

③优化后的双指针

相比于上面的方式，我们使用了双指针的方式进行，但是你要考虑一个点，就是我们添加了新的数组，也就是将空间复杂度变为了O(n)，那么我们是不是可以不添加新的数组也可以完成，也就是在O(1)的空间复杂度下也可以完成我们的操作？

当然是可以的，我们可以使用从后往前便利的方式进行，因为原来的num1数组中本来就可以存放num1+num2中的所有元素，所以我们只需要从后往前进行遍历就可以了！

代码展示

①使用API --- arraycopy

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

    System.arraycopy(nums2,0,nums1,m,n);   //这里表示的意思是，我们从nums2中的第0位开始复制，复制到nums1的第m位开始，总共复制n个数据
    Array.sort(nums1);
    return nums1;    

}

但是这个方法时间复杂度为O((m+n)log(m+n))

②使用双指针

public static int[] merge1(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;   //指向nums1_copy
    int p2=0;   //指向nums2 
    int p=0;    //指向nums1
    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<m){
        System.arraycopy(nums2,2,nums1,p1+p2,m+n-p1-p2);
    }
}

③优化的双指针

我们可以从后往前进行遍历，这样就不用使用额外的空间了！

public static int[] merge2(int nums1,int m,int nums2,int n){
    int p=nums.length;
    int p1=m-1;  //指向数组nums1的最后一个位置
    int p2=n-1;  //指向数组nums2的最后一个位置
    while(p1>=0&&p2>=0)
    {
        nums1[p--]=nums1[p1]>nums[p2]?nums1[p1]:nums[p2];
    }
    System.arraycopy(nums2,0,nums1,0,p2+1);
    return nums1;
}

总结

在这里我们可以发现熟悉底层API很重要，而且我们会发现双指针的应用很广泛！