归并

核心思路：依次比较，取较小值放入新数组中
i 遍历nums1 ， j 遍历nums2 ，取较小值放入nums3中
那如果nums[i] 和nums[j]中相等，随便放一个到nums3

在这里插入图片描述

那如果nums[i] 和nums[j]中相等，随便放一个到nums3

在这里插入图片描述

此时 nums1 中的元素已经走完了，那么直接把 nums2 中剩下的元素拿到 nums3 中去,
因为nums2 是有序数组，所以不需要考虑 nums2剩下的元素比nums3小

在这里插入图片描述

这总方法最大的问题就是新开辟了一个数组如果题目要求空间复杂度为O(1) ，这种方法就不管用了

思路二

归并依次比较取较小值 ,但是思路二是依次比较取较大值
思路二和归并大体上相似 ,

思路二整体思路：
i 指向nums1最后一个有效元素 ,向前遍历，
j 指向nums2最后一个有效元素，向前遍历
dst指向nums1 的最后一个元素 ,也是向前遍历
j 指向的元素如果大于 i 指向的元素，那么就把 j 指向的元素放入 dst 指向的位置中去

在这里插入图片描述

当j 向前遍历完nums2时，我们直接让它结束就行了

但是还需要多考虑一种情况

在这里插入图片描述

当nums1中的每一个元素都比nums2中的每一个元素大，nums1 一定会先遍历完，这时候就需要将nums2 的每一个元素提前放入nums1中

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
  int i = m -1 ;
  int j = n- 1 ;
  int dst = m + n -1 ;
  while( i >=0 && j >= 0)
  {
      //nums2先走完 , j < 0 
      if( nums1[i]>= nums2[j])  //取较大值
      {
          nums1[dst] = nums1[i];
          dst-- ;
          i--;
      }
      else
      {
          nums1[dst]=nums2[j];
          dst--;
          j--;
      }
  }
    // nums1 先走完 , i < 0 
    while( j>=0 )
    {
        nums1[dst] = nums2[j];
      j -- ;
      dst -- ;
    }
}