88. Merge Sorted Array 合并排序数组

题目

给定两个以非递减序列排序的数组 nums1 和 nums2，m和n分别表示取 nums1 和 nums2 的元素个数。
以非递减序列合并两个数组，将最终的结果存储到 nums1 中，为了适应这一点，nums1 的长度为 m+n。

解析

在不使用额外空间的情况下，对于一个有序列表使用插入排序可以完成。但是时间复杂度会提高，考虑这两个有序数组，本来可以通过O(m+n)的时间复杂度完成，但是因为空间不足的问题，需要使用插入排序。有没有办法解决空间问题。

因为 nums1 是足够长的，我们考虑将 nums1 先移动到数组的末尾，这样预留出来的位置无论如何都能满足 nums2 的长度，然后采用 O(m+n)复杂度的排序，最终我们能完成这个nums1数组，最后复杂度为O(m+m+n)

1. 首先将 nums1 整体右移 n 个单位
2. 记当前 nums1 的起始指针为 p，nums2 起始指针为 q，结果指针为 i
## 伪代码

move(nums1, n)
p = n
q = 0
for p<m+n && q < n
if nums1[p] < nums2[q]
nums1[i] = nums1[p]
p++
else
nums1[i] = nums2[q]
q++
i++
if p < m+n
nums1[i]=nums1[p]
i++,p++
if q <n
nums1[i]=nums2[q]
i++,p++

代码

func merge(nums1 []int, m int, nums2 []int, n int)  {
    for i:=0;i<m;i++ {
        nums1[m+n-i-1] = nums1[m-i-1]
    }
    p:=n
    q:=0
    i:=0
    for p<m+n && q < n {
        if nums1[p] < nums2[q] {
            nums1[i] = nums1[p]
            p++
        }else {
            nums1[i] = nums2[q]
            q++
        }
        i++
    }
    for p<m+n {
        nums1[i] = nums1[p]
        p++
        i++
    }
    for q<n {
        nums1[i] = nums2[q]
        q++
        i++
    }
}