题目描述

给定两个有序的整数数组nums1和nums2，要求将nums2合并进nums1中，并使nums1有序。

注意：
你可以假设nums1有足够的空间（大于或等于m + n）来保存nums2中的其他元素。 nums1和nums2中初始化的元素数量分别为m和n。

样例

输入 

nums1: 1 3 5 7
nums2: 2 4 6 7

输出

nums1: 1 2 3 4 5 6 7 7

算法1

(线性合并) 时间复杂度 $O(m+n)$, 空间复杂度$O(1)$

1. 设置cur指针指向合并后的nums1数组(大小为m+n)的最后一个元素，p指向合并前的nums1数组(大小为m)的最后一个元素，q指向nums2数组(大小为n)的最后一个元素。
2. 比较p指向的值和q指向的值，将大的值挪进nums1[cur]。
3. cur指针往前挪，p或者q指针也相应往前挪。
4. 循环以上步骤直到p=0或q=0
5. 若q>=0,将nums2数组剩余的元素挪进nums1。

C++ 代码

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p = m - 1 , q = n - 1 , cur = m + n - 1 ;
        while(p>= 0 && q >= 0){
            nums1[cur--] = ( nums1[p] >= nums2[q] ? nums1[p--] : nums2[q--]);
        }
        while(q >= 0){
            nums1[cur--] = nums2[q--];
        }
    }
};