题目描述
两个有序整数数组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很重要，而且我们会发现双指针的应用很广泛！
|