Leetcode. 88合并两个有序数组-Toy模板网

这篇具有很好参考价值的文章主要介绍了Leetcode. 88合并两个有序数组。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

合并两个有序数组

归并

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

Leetcode. 88合并两个有序数组

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

Leetcode. 88合并两个有序数组

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

Leetcode. 88合并两个有序数组

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

思路二

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

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

Leetcode. 88合并两个有序数组

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

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

Leetcode. 88合并两个有序数组

当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 -- ;
    }
}