LeetCode 88 合并两个有序数组

1. 题目地址

    https://leetcode.cn/problems/merge-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150

2. 题解

    这道题跟归并排序的归并操作非常类似。（具体内容可以查看我的博客，这里不再赘述。）但是有一个需要注意的点：
        1.  尽量不要用额外空间。
    我们发现，第一个数组的长度为n+m。这就代表第一个数组可以容纳下第一个第二个数组的所有元素。
    因此，我们可以将两个数组均从最后一个元素开始往前遍历。每次遍历的时候，将二者最大的元素放在第一个数组最后的位置。
    在遍历的过程中，会出现两种情况：
        1.  第一个数组遍历完，第二个数组没有遍历完。那么就将第二个数组剩余的元素依次放入第一个数组即可。
        2.  第二个数组遍历完，第一个数组没有遍历完。这种情况实际上我们不需要处理。因为，第一个数组剩余的元素已经位于正确的位置了。

3. 代码

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int k = n + m - 1;
        int i = m - 1;
        int j = n - 1;
        while(i >= 0 && j >= 0){
            if(nums1[i] >= nums2[j]){
                nums1[k--] = nums1[i--];
            }else{
                nums1[k--] = nums2[j--];
            }
        }
        while(j >= 0){
            nums1[k--] = nums2[j--];
        }
    }
};