你好！我是你的OI竞赛金牌教练。

这道题在LeetCode上是《合并两个有序数组》，在NOI/NOIP竞赛体系中，这是一道非常经典的考察线性表操作、**双指针（Two Pointers）以及原地算法（In-place Algorithm）**思维的基础题。

虽然题目看似简单，直接调用 std::sort 也能过，但竞赛训练中我们关注的是如何利用 “有序” 这一性质，将时间复杂度优化到 $O(N)$，并将空间复杂度优化到 $O(1)$。特别是 “逆向双指针” 技巧，是后续解决复杂区间合并问题的基础。

题目：合并两个有序数组 (Merge Sorted Array)

题目描述

给定两个非递减顺序排列的整数数组 nums1 和 nums2，其中 nums1 的初始有效元素个数为 $m$，nums2 的初始有效元素个数为 $n$。

请你原地合并 nums2 到 nums1 中，使合并后的 nums1 成为一个非递减顺序排列的数组。

注意： 为了应对合并后的数据，nums1 的实际长度被设计为 $m + n$。其中前 $m$ 个元素表示应合并的有效数据，由于我们希望原地修改，nums1 后面的 $n$ 个位置虽然在输入中可能被占位（通常为0），但在逻辑上应视为“空闲空间”，用于存放合并后的结果。

输入格式

第一行包含两个整数 $m$ 和 $n$，分别表示 nums1 和 nums2 中有效元素的个数。 第二行包含 $m$ 个整数，表示 nums1 的初始有效序列。 第三行包含 $n$ 个整数，表示 nums2 的初始有效序列。 (注：在实际评测系统的内存模型中，nums1 数组已被预分配了 $m+n$ 的空间，不仅仅是输入的 $m$ 个数)

输出格式

输出一行，包含 $m + n$ 个整数，表示合并后按非递减顺序排列的 nums1 数组的所有元素。整数之间用空格分隔。

样例输入 1

3 3
1 2 3
2 5 6

样例输出 1

1 2 2 3 5 6

样例说明：需要合并的序列是 [1, 2, 3] 和 [2, 5, 6]。合并结果是 [1, 2, 2, 3, 5, 6]。

样例输入 2

1 0
1

(注：这里第二行为空行，表示nums2为空)

样例输出 2

1

样例输入 3

0 1

1

(注：这里第一行为空行，表示nums1初始有效元素为空)

样例输出 3

1

数据范围与提示

• $0 \le m, n \le 200$
• $1 \le m + n \le 200$
• $-10^9 \le nums1[i], nums2[i] \le 10^9$
• 进阶挑战：你可以设计一个时间复杂度为 $O(m + n)$ 且额外空间复杂度为 $O(1)$ 的算法来解决此问题吗？

教练的解题思路提示 (Pseudo-code)

这道题有三种解法，这也代表了三种思维层次：

1. 青铜解法（暴力排序）：先把 nums2 里的数全部追加到 nums1 后面，然后直接调用 std::sort。时间复杂度 $O((m+n)\log(m+n))$，没有利用“数组已有序”的特性。
2. 白银解法（正向双指针 + 辅助空间）：开一个新数组，同时遍历 nums1 和 nums2，谁小就把谁放进去。最后再拷回 nums1。时间 $O(m+n)$，但空间是 $O(m+n)$ 或 $O(m)$，不满足原地操作的最优要求。
3. 王者解法（逆向双指针 + 原地操作）：
   • 这是本题的核心考点。
   • 如果从前往后填，nums1 的有效数据可能会被覆盖，导致需要频繁移动数据。
   • 关键洞察：nums1 的尾部是空的！所有的空闲位都在后面。
   • 我们定义三个指针：p1 指向 nums1 有效数据的末尾，p2 指向 nums2 的末尾，tail 指向 nums1 总长度的末尾。
   • 倒着比较：比较 p1 和 p2 指向的值，谁大就把谁填入 tail 的位置，然后该指针前移。
   • 这样可以保证不需要任何额外空间，也不会覆盖还没用到的 nums1 数据。

NOI风格 伪代码提示 (Chinese Keywords)

函数 merge(整数数组 nums1, 整数 m, 整数数组 nums2, 整数 n):
    // 初始化三个指针
    // p1 指向 nums1 的有效数据末尾 (即下标 m-1)
    // p2 指向 nums2 的有效数据末尾 (即下标 n-1)
    // tail 指向 nums1 的最终物理末尾 (即下标 m+n-1)
    
    定义整数变量 p1 = m - 1
    定义整数变量 p2 = n - 1
    定义整数变量 tail = m + n - 1

    // 核心逻辑：逆向归并
    // 只要两个数组里都还有没处理完的元素，就进行比较
    当 (p1 >= 0 并且 p2 >= 0) 时循环执行：
        
        // 比较两边的尾部元素，谁大谁就去占领 tail 的位置
        如果 (nums1[p1] > nums2[p2]) 则：
            nums1[tail] = nums1[p1]
            p1 = p1 - 1
        否则：
            nums1[tail] = nums2[p2]
            p2 = p2 - 1
        结束如果
        
        // 填完一个位置，尾部指针前移
        tail = tail - 1
    结束循环

    // 易错点处理 / 边界情况
    // 思考：如果 p1 先用完了，剩下 p2 里的元素怎么办？
    // 答：需要把 p2 剩下的元素直接拷贝到 nums1 的前面。
    // 思考：如果 p2 先用完了，剩下 p1 里的元素怎么办？
    // 答：不用动！因为它们本身就在 nums1 里，且位置正确（有序）。
    
    // 只需要处理 p2 剩余的情况
    当 (p2 >= 0) 时循环执行：
        nums1[tail] = nums2[p2]
        p2 = p2 - 1
        tail = tail - 1
    结束循环

结束函数

知识点总结 (Knowledge Points)

在备战 NOI/CSP 时，通过此题你需要掌握：

1. 双指针法 (Two Pointers)：

   • 这是处理有序数组、链表合并问题的标准范式。
   • 理解为什么双指针能将复杂度从 $O(N \log N)$ 降至 $O(N)$。

2. 原地算法 (In-place Algorithm)：

   • 理解空间复杂度的概念。
   • 逆向思维：当正向操作遇到“数据覆盖”或“大量移动”的困难时，尝试从后往前操作往往能利用空闲空间，解决冲突。

3. 边界条件处理：

   • 考虑 $m=0$ 或 $n=0$ 的情况。
   • 上述伪代码中的第二个 while 循环就是为了处理其中一个数组提前遍历结束的边界情况。

4. 数组内存模型：

   • 理解题目中 nums1 长度为 $m+n$ 的含义，这在 C++ std::vector 的 resize 或 C 语言数组定义中非常常见。