合并两个有序数组

题目链接: https://leetcode.cn/problems/merge-sorted-array/

解题思路：

1. 题目要求将nums2合并入nums1，时间复杂为O(n+m)，因此必然不能是从前往后合并，从前往后合并需要插入后将后续的元素逐个后移，时间复杂度遍不会是O(n+m)

2. nums1中在数组后预留了足够的空间用于存放nums2，因此在合并数组时可以不考虑将nums2数据写入nums1中时覆盖未处理数据

3. 此处仅需从后往前逐个对比nums1以及nums2的数据，写入大的数据，并下标减一即可，具体实现如下

func merge(nums1 []int, m int, nums2 []int, n int)  {
    // 从nums1末尾开始写入
    length:=len(nums1)-1
    m=m-1
    n=n-1
    for ;n>=0&&m>=0;{
        if nums1[m]>nums2[n]{
            nums1[length]=nums1[m]
            m--
        }else{
            nums1[length]=nums2[n]
            n--
        }
        length--
    }
    // 若nums1中数据已经完全处理完，则直接灌入nums2的数据
    for ;n>=0;n--{
        nums1[length]=nums2[n]
        length--
    }
}

也可以使用一些函数

func merge(nums1 []int, m int, nums2 []int, n int)  {
    copy(nums1[m:], nums2)
    sort.Ints(nums1)
}

复杂度分析

• 时间复杂度: $O(n)$

• 空间复杂度: $O(1)$