LeetCode每日一题：合并两个有序数组

第一种解法，我第一眼看到这个就想到了插入排序法，因为nums1是有序的，所以只需要考虑nums2的插入即可，相当于已经帮你排好了m个数，从第m+1个数开始插入

• 代码实现;

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

   int mIndex = m;       
   int a = m;
 for(int i = 0;i < n ;i++){    
    mIndex = a;    
   while(mIndex > 0){
      if(nums1[mIndex - 1] > nums2[i]){
          nums1[mIndex] = nums1[mIndex - 1];
          mIndex--;
      }else{
          break;
      }
   }
   nums1[mIndex] = nums2[i];
   a++;
 }
}
}

但是仔细想想的话发现我并没有用到nums2这个数组也是有序的条件，所以第一种方法还是不行的，必须把所有能用到的条件都用起来，于是有了第二种解法，第二种解法的思路是，用nums2数组的数与nums1里面的最后一个数(及最大的那一个数)比较，如果比它大就直接放到nums1的最后(m+n-1)，如果比它小就后移一位

• 第二种解法代码实现：

class Solution {
 public void merge(int[] nums1, int m, int[] nums2, int n) {
    // 三指针 指针一p1、nums1有效元素尾部；指针二p2、nums2尾部；指针三p3、最终数组尾部
    // 1.当，p1>=0时，nums[p1],nums[p2]对比
    // 1.1 nums[p1]大，将nums[p1]放入p3位置。p1--,p3--
    // 1.2 nums[p2]大于等于nums[p1]，将nums[p2]放入p3位置。p2--,p3--
    // 2.当，p1<0时，将nums[p2]放入p3位置。p2--,p3--
    // 循环结束条件：p2<0
    
    int p1=m-1,p2=n-1,p3=m+n-1;
    while(p2 >= 0){
        if(p1 >= 0 && nums1[p1] > nums2[p2]){
            nums1[p3--] = nums1[p1--];
        } else {
            nums1[p3--] = nums2[p2--];
        }
    }
}
}

代码一下就简单了许多，所以一定要把所有能用上的条件都用上，才能达到最好的代码