合并两个有序数组

给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 num1 成为一个有序数组。

说明:

初始化 nums1nums2 的元素数量分别为 mn 。 你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n )来保存 nums2 中的元素。

示例:

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

输出: [1,2,2,3,5,6]

解题思路:

  • nums1nums2 有序,若把 nums2 全部合并到 nums1 ,则合并后的 nums1 长度为 m+n
  • 我们可以从下标 m+n-1 的位置填充 nums1 ,比较 nums1[len1]nums2[len2] 的大小,将最大值写入 nums1[len],即
    • nums1[len1]>=nums2[len2]nums1[len--] = nums1[len1--] ,这里 -- 是因为写入成功后,下标自动建议,继续往前比较
    • 否则 nums1[len--] = nums2[len2--]
  • 边界条件:
    • len1 < 0,即 len2 >= 0 ,此时 nums1 已重写入, nums2 还未合并完,仅仅需要将 nums2 的剩余元素(0…len)写入 nums2 即可,写入后,合并完成
    • len2 < 0,此时 nums2 已全部合并到 nums1 ,合并完成

时间复杂度为 O(m+n)

代码实现:

const merge = function(nums1, m, nums2, n) {
    let len1 = m - 1,
        len2 = n - 1,
        len = m + n - 1
    while(len2 >= 0) {
        if(len1 < 0) {
            nums1[len--] = nums2[len2--]
            continue
        }
        nums1[len--] = nums1[len1] >= nums2[len2] ? nums1[len1--]: nums2[len2--]
    }
};