LeetCode-88

题目
给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。
为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,4,5], n = 3
输出：[1,2,2,3,4,5]
解释：需要合并 [1,2,3] 和 [2,4,5] ，合并结果是 [1,2,2,3,4,5] 。

由题可知数组 nums1 和 nums2 均已排序，合并这两个有序数组可以采用双指针的思想，将其看作两个队列，每次比较出这两个队列队首较小的元素，放入结果中，即可得到合并后的有序数组。

设置两个指针 p1 和 p2 作为队列的头指针，指针从前往后依次移动，若其中一个数组遍历完成，则将另一个数组剩余元素全部加入合并数组结果中。

在方法1中需要使用临时变量，是为了避免还未处理的数组元素被合并后的结果覆盖。注意到在 nums1 中需要使用的元素均位于数组的前半部分，后半部分为空，因此可以考虑将合并后的结果先放入后半部分，即指针从后向前遍历，每次取出两者中较大的元素放入 nums1 数组末尾，不会产生 nums1 元素被覆盖的情况。

设置两个指针 p1 和 p2 作为队列的尾指针，指针从后往前依次移动，若其中一个数组遍历完成，则将另一个数组剩余元素全部加入合并数组结果中。

更多题解

1. 判断 p1==m ：nums1 数组遍历完成，则遍历 nums2 数组，将其剩余元素依次加入结果中。
2. 判断 p2==n ：nums2 数组遍历完成，则遍历 nums1 数组，将其剩余元素依次加入结果中。
3. 判断 nums1[p1] < nums2[p2] ：nums1 队首元素小于 nums2 队首元素，则取 nums1 队首元素加入到结果中，继续进行下一轮比较。
4. 判断 nums1[p1] > nums2[p2] ：nums2 队首元素小于 nums1 队首元素，则取 nums2 队首元素加入到结果中，继续进行下一轮比较。

class Solution {
public:
    void merge(vector& nums1, int m, vector& nums2, int n) {
        int p1 = 0, p2 = 0;
        //定义临时变量，避免覆盖数组元素
        int sorted[m + n];
        int cur;
        //双指针遍历两数组
        while (p1 < m || p2 < n) {
            if (p1 == m) {
                cur = nums2[p2++];
            } else if (p2 == n) {
                cur = nums1[p1++];
            } else if (nums1[p1] < nums2[p2]) {
                cur = nums1[p1++];
            } else {
                cur = nums2[p2++];
            }
            // p1: nums1中已遍历的元素数目
            // p2: nums2中已遍历的元素数目
            sorted[p1 + p2 - 1] = cur;
        }
        // 合并后数组放至 nums1 中
        for (int i = 0; i != m + n; ++i) {
            nums1[i] = sorted[i];
        }
    }
};

1. 判断 p1==-1 ：nums1 数组遍历完成，则遍历 nums2 数组，将其剩余元素依次加入结果中。
2. 判断 p2==-1 ：nums2 数组遍历完成，则遍历 nums1 数组，将其剩余元素依次加入结果中。
3. 判断 nums1[p1] > nums2[p2] ：nums1 队尾元素大于 nums2 队尾元素，则取 nums1 队尾元素加入到结果中，继续进行下一轮比较。
4. 判断 nums1[p1] < nums2[p2] ：nums2 队尾元素大于 nums1 队尾元素，则取 nums2 队尾元素加入到结果中，继续进行下一轮比较。

class Solution {
public:
    void merge(vector& nums1, int m, vector& nums2, int n) {
        int p1 = m - 1, p2 = n - 1;
        int tail = m + n - 1;
        int cur;
        // 双指针遍历两数组
        while (p1 >= 0 || p2 >= 0) {
            if (p1 == -1) {
                cur = nums2[p2--];
            } else if (p2 == -1) {
                cur = nums1[p1--];
            } else if (nums1[p1] > nums2[p2]) {
                cur = nums1[p1--];
            } else {
                cur = nums2[p2--];
            }
            nums1[tail--] = cur;
        }
    }
};