力扣面试经典——88题

给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n，分别表示 nums1 和 nums2 中的元素数目。

请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。

⚠️ 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0，应忽略。nums2 的长度为 n。

---

🧪 示例说明

示例 1：

输入：
nums1 = [1, 2, 3, 0, 0, 0], m = 3
nums2 = [2, 5, 6], n = 3

输出：
[1, 2, 2, 3, 5, 6]

解释：需要合并 [1,2,3] 和 [2,5,6]。
合并结果是 [1, 2, 2, 3, 5, 6]，其中斜体加粗标注的为 nums1 中的原始元素。

示例 2：

输入：
nums1 = [1], m = 1
nums2 = [], n = 0

输出：
[1]

示例 3：

输入：
nums1 = [0], m = 0
nums2 = [1], n = 1

输出：
[1]

解释：因为 m = 0，所以 nums1 中没有有效元素。0 只是为了确保合并结果可以顺利存放到 nums1 中。

---

🔍 提示：

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• -10^9 <= nums1[i], nums2[j] <= 10^9

---

🚀 进阶挑战：

你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？

---

💡 参考代码：

/**
 * 合并两个已排序的数组
 * 将 nums2 合并到 nums1 中，结果存储在 nums1 内
 * 
 * @param nums1     目标数组，预分配了足够空间 (长度为 m+n)
 * @param nums1Size nums1 数组的总长度 (等于 m+n)
 * @param m         nums1 中有效元素的个数
 * @param nums2     源数组，包含需要合并的元素
 * @param nums2Size nums2 数组的长度 (等于 n)
 * @param n         nums2 中元素的个数
 */
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    // 初始化三个指针：i指向nums1有效元素末尾，j指向nums2末尾，k指向合并结果末尾
    int i = m - 1;      // nums1有效元素的最后一个索引
    int j = n - 1;      // nums2的最后一个索引
    int k = m + n - 1;  // 合并后数组的最后一个索引
    
    // 从后往前比较两个数组的元素，将较大者放到nums1的末尾
    while (i >= 0 && j >= 0) {
        if (nums1[i] > nums2[j]) {
            nums1[k--] = nums1[i--];  // nums1[i]较大，将其放到位置k
        } else {
            nums1[k--] = nums2[j--];  // nums2[j]较大或相等，将其放到位置k
        }
    }
    
    // 如果nums2中还有剩余元素，复制到nums1中
    // 注意：如果nums1有剩余元素(i>=0)，它们已经在正确位置，无需移动
    while (j >= 0) {
        nums1[k--] = nums2[j--];
    }
}

📖 总结：

点击展开题目总结

🤔 合并两个有序数组

---

1️⃣ 题目核心信息

🎯 功能描述：将两个已排序的数组合并成一个有序数组，结果存储在第一个数组中

📥 输入输出：

• 输入：两个已排序数组 nums1 和 nums2，以及它们的有效元素个数 m 和 n
• 输出：无返回值，合并结果直接存储在 nums1 中

---

2️⃣ 实现原理

💡 核心思路：采用从后往前的双指针技术，避免覆盖未处理的数据

📋 实现步骤：

1. 设置三个指针分别指向两个数组有效元素末尾和合并结果末尾
2. 从后往前比较两个数组的元素，将较大者放到合并位置
3. 处理剩余未合并的元素

---

3️⃣ 关键点解析

🔁 为什么需要两个循环

第一个循环会在任意一个数组处理完时停止，但另一个数组可能还有剩余元素需要处理。

📌 具体例子

nums1 = [4,5,6,0,0,0] (m=3) nums2 = [1,2,3] (n=3)

🔄 执行过程：

1. 比较 6 和 3 → nums1[5] = 6
2. 比较 5 和 3 → nums1[4] = 5
3. 比较 4 和 3 → nums1[3] = 4

此时第一个循环结束，但nums2中[1,2,3]还没有被处理。

⚡ 关键理解

当第一个循环结束时，有两种可能情况：

• i < 0 但 j >= 0：nums1处理完了，但nums2还有剩余元素需要复制
• j < 0 但 i >= 0：nums2处理完了，但nums1还有剩余元素

对于第二种情况，nums1的剩余元素已经处于正确位置，无需移动，所以不需要额外处理。

因此需要第二个循环来处理nums2的剩余元素。

🎯 代码技巧

• 从后往前遍历避免了覆盖 nums1 中未处理的元素
• 只需处理 nums2 的剩余元素，因为 nums1 的剩余元素已在正确位置
• 使用 -- 操作符在赋值的同时移动指针，代码更简洁

---

4️⃣ 使用场景

✅ 适用情况：

• 需要合并两个已排序的数组
• 希望在原地进行合并操作以节省空间
• 处理数组相关的归并排序问题

⚠️ 前提条件：

• nums1 必须有足够空间容纳合并结果（至少 m+n 个元素）
• 两个输入数组都已按非递减顺序排序

---

5️⃣ 复杂度分析

⏱️ 时间复杂度：O(m + n)，每个元素最多被访问一次

💾 空间复杂度：O(1)，只使用了常数个额外变量

---

6️⃣ 注意事项

🚩 边界情况：

• m = 0：nums1 为空数组
• n = 0：nums2 为空数组
• 其中一个数组的所有元素都比另一个数组小

💥 易错点：

• 忘记处理剩余元素，特别是第二个循环
• 指针边界条件判断错误
• 从前往后合并导致数据被覆盖

加载评论中...