面试必刷的数组三连：原地删除与合并

坚持用 清晰易懂的图解 + 多语言代码，让每道题变得简单！
呆头个人主页详情
呆头个人Gitee代码仓库
呆头详细专栏系列
座右铭： “不患无位，患所以立。”

面试必刷的数组三连：原地删除与合并

• 前言
• 目录
• 1.移除元素
• 2.删除有序数组中的重复项
• • • 关键点
    • 详细步骤（以 `nums = [1, 1, 2, 2, 3]` 为例）
    • 为什么 `nums[i] == nums[k]` 时，`k` 不移动？
    • 总结
• 3.合并两个有序数组
• • • 解决思路
    • 解决代码
    • 代码解释
    • 示例
    • 复杂度分析

前言

🚀 你好，欢迎来到《编程闯关记》！
这里是算法与数据结构的实战基地，也是你从“暴力解法”到“最优解”的进化场。

🔍 专栏初衷：

• 用清晰的图解 + 多语言代码（Python/Java/C++/C），拆解每道题背后的逻辑。
• 不只讲“怎么做”，更讲“为什么”——从题目分析、边界条件到复杂度优化。
• 适合想夯实基础或突击面试的你，尤其针对LeetCode/牛客高频题！

💡 如何使用本专栏：
1️⃣ 先独立思考：尝试自己写出第一版代码（哪怕很烂）。
2️⃣ 对比解法：看看我的思路和你的差异，吸收优化技巧。
3️⃣ 举一反三：每篇末尾会附相似题目链接，趁热打铁。

📌 坚持打卡：
算法没有捷径，但正确的方法能让你少走弯路。每天15分钟，和我一起用代码雕刻思维！

（正文开始👇）

目录

1.移除元素

力扣链接直达<请点击

int removeElement(int* nums, int numsSize, int val) { int count = 0; for(int i=0;i<numsSize;i++) { if(nums[i]!=val) { nums[count] = nums[i]; count++; } } return count;}

代码说明：

• 初始化计数count： count从0开始，用于记录不等于val的元素数量，并作为新数组的索引。

• **遍历数组：**使用i遍历整个数组，检查每个元素是否等于val。

• 如果nums[i]不等于val，则将其复制到nums[k]的位置，并递增k。

• 如果等于val，则跳过该元素。

• 返回结果：最终k即为新数组的长度，且数组的前k个元素均为不等于val的元素。

这种方法高效且满足题目要求的原地修改条件。

2.删除有序数组中的重复项

力扣链接直达<请点击

int removeDuplicates(int* nums, int numsSize) { if (numsSize == 0) return 0; // 空数组直接返回 0 int k = 0; // 慢指针，初始指向第一个元素 for (int i = 1; i < numsSize; i++) { if (nums[i] != nums[k]) { // 发现新元素 k++; // 移动慢指针 nums[k] = nums[i]; // 存入新元素 } // 如果 nums[i] == nums[k]，跳过（i 继续前进） } return k + 1; // 返回去重后的长度}

在 “原地移除重复元素” 的算法中，当遇到重复元素时，并不是真的删除它，而是通过 覆盖（跳过） 的方式，让后面的非重复元素占据前面的位置，最终只保留不重复的部分。

关键点

1. 不真正删除元素：数组在内存中是连续的，不能直接删除某个元素，只能覆盖。
2. 双指针策略：
   • 慢指针 k：记录 不重复元素应该存放的位置。
   • 快指针 i：遍历数组，检查是否有新元素。
3. 覆盖重复元素：
   • 如果 nums[i] 是新元素（即 nums[i] != nums[k]），就把它存到 nums[k+1]，然后 k++。
   • 如果 nums[i] 是重复的（即 nums[i] == nums[k]），就 跳过它（i 继续前进，k 不动）。

详细步骤（以 nums = [1, 1, 2, 2, 3] 为例）

最终结果：

• 前 k+1 = 3 个元素是去重后的：[1, 2, 3]（后面的 2, 3 可以忽略）。
• 返回 k + 1 = 3（去重后的长度）。

为什么 nums[i] == nums[k] 时，k 不移动？

• k 指向的是当前不重复部分的最后一个元素。
• 如果 nums[i] 和 nums[k] 相同，说明 nums[i] 是重复的，直接跳过（不存入数组）。
• 只有遇到新元素时，才存入 nums[k+1] 并移动 k。

总结

• 移除重复元素 实际上是 用后面的不重复元素覆盖前面的重复位置。
• k 的作用：
  • 记录 去重后的数组末尾位置。
  • 只有遇到新元素时才移动 k，否则跳过。
• 时间复杂度 O(n)，空间复杂度 O(1)（原地修改）。

这样，最终 nums 的前 k+1 个元素就是去重后的结果，而后面部分可以忽略。

3.合并两个有序数组

力扣链接直达<请点击

解决思路

由于 nums1 有足够的空间容纳 nums2 的元素，我们可以利用 双指针 的方法从后向前合并，以避免覆盖 nums1 中还未处理的元素。具体步骤如下：

1. 初始化指针：

   • i 指向 nums1 的最后一个有效元素（即 m - 1）。
   • j 指向 nums2 的最后一个元素（即 n - 1）。
   • k 指向 nums1 的最后一个位置（即 m + n - 1）。

2. 从后向前比较并合并：

   • 比较 nums1[i] 和 nums2[j]，将较大的元素放到 nums1[k]。
   • 移动相应的指针（i 或 j）和 k。

3. 处理剩余元素：

   • 如果 nums2 中还有剩余元素（即 j >= 0），直接复制到 nums1 的前面。

解决代码

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { 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--]; } else { nums1[k--] = nums2[j--]; } } // 如果 nums2 还有剩余元素，直接复制到 nums1 的前面 while (j >= 0) { nums1[k--] = nums2[j--]; }}

代码解释

1. 初始化指针：

   • i 从 nums1 的有效末尾开始。
   • j 从 nums2 的末尾开始。
   • k 从 nums1 的最后一个位置开始。

2. 比较并合并：

   • 比较 nums1[i] 和 nums2[j]，将较大的元素放入 nums1[k]，并移动相应的指针。
   • 这样确保 nums1 的后半部分不会被覆盖，直到所有元素正确归位。

3. 处理剩余元素：

   • 如果 nums2 中还有元素未合并（即 j >= 0），直接复制到 nums1 的前面，因为 nums1 的前面部分已经处理完毕。

示例

输入：

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

执行过程：

1. i = 2, j = 2, k = 5：
   • nums1[2] = 3 < nums2[2] = 6 → nums1[5] = 6, j--, k--
2. i = 2, j = 1, k = 4：
   • nums1[2] = 3 < nums2[1] = 5 → nums1[4] = 5, j--, k--
3. i = 2, j = 0, k = 3：
   • nums1[2] = 3 > nums2[0] = 2 → nums1[3] = 3, i--, k--
4. i = 1, j = 0, k = 2：
   • nums1[1] = 2 == nums2[0] = 2 → nums1[2] = 2, j--, k--
5. j = -1，循环结束。
6. nums2 已无剩余元素，合并完成。

最终结果：

nums1 = [1, 2, 2, 3, 5, 6]

复杂度分析

• 时间复杂度：O(m + n)，每个元素最多被比较一次。
• 空间复杂度：O(1)，没有使用额外空间，原地修改 nums1。

这种方法高效且避免了不必要的元素移动，是最优解。