88合并两个有序数组
刷题链接：https://leetcode-cn.com/problems/merge-sorted-array/
在这里提供两套解题思路：
-
直接将nums1后续的值填满，调用Arrays.sort()函数直接进行排序。
使用该方法解题的关键：如何把nums2的值成功赋值到nums1的末尾呢，关注索引。
首先，我们能够得到nums1的总长度nums1.length或者m+n，nums1第一个为0的值即为m，也就是说循环的起点为m。而nums2如何获取它的索引呢，首先能够获得nums1的最大索引m+n-1，nums2[m+n-1-m]即可获得nums2[n-1]最末的一个数字，然后令i=m，i不断++，则可不断获得n-1，n-2，n-3的值。即可成功解题。
|
public void merge(int[] nums1, int m, int[] nums2, int n) {
for(int i=m;i<m+n;i++){
nums1[i]=nums2[m+n-i-1]; }
Arrays.sort(nums1); }
|
但是这个方法时间空间复杂度较低，所以这里提供解题思路2索引指针。
-
索引指针
1 2 3 0 0 0
2 5 6
由于数组已经是排好顺序的，最末尾的元素必定时最大的，我们只要对最末尾的元素进行比较，将最末尾的元素放到最尾端，然后不断进行比较即可，而这里我们需要用到3个指针。一个指针指向nums1数组的最后一个值，一个指向nums1的nums1[m-1]值，一个指向nums2[n-1]。
指针索引注意细节：
当橙色指针的索引小于0时，数组已经排好顺序了。
|
public void merge(int[] nums1, int m, int[] nums2, int n) { int i1=m-1; int i2=n-1; int cur=nums1.length-1;
//不用观察i1是否小于等于0，因为当i1小于等于0时，i2仍然继续执行 //i2小于0时，i1已经拍好顺序了 while (i2>=0){ if(i1>=0&&nums1[i1]>=nums2[i2]){ nums1[cur--]=nums1[i1--]; }else{// i1 < 0 || nums2[i2] >= nums1[i1] nums1[cur--]=nums2[i2--]; } } }
|