合并两个有序数组需在原地将 nums2 并入 nums1 并保持非递减顺序。核心方案使用从后向前的双指针技巧，比较末尾元素填入空位，避免覆盖有效数据。该方法时间复杂度 O(m+n)，空间复杂度 O(1)，是考察双指针与边界处理的经典面试题。
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，以及两个整数 m 和 n。
nums1 的长度为 m + nm 个元素为有效元素n 个元素为 0（占位）nums2 长度为 n要求：
将 nums2 合并到 中，使结果仍然保持非递减顺序。
nums1注意： 必须 原地修改 nums1，不能返回新数组。
输入： nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3
输出： [1,2,2,3,5,6]
输入： nums1 = [1], m = 1 nums2 = [], n = 0
输出： [1]
输入： nums1 = [0], m = 0 nums2 = [1], n = 1
输出： [1]
很多人第一反应：
从前往后比较，小的放前面。
问题是：
举例：
nums1 = [1,2,3,0,0,0] nums2 = [2,5,6]
如果从前面开始插入，后面的 3 可能会被覆盖。
关键思想：
既然后面有空位，那就从后往前填！
i = m - 1 // nums1 有效元素最后一个 j = n - 1 // nums2 最后一个 k = m + n - 1 // nums1 总数组最后一个位置
示例：
nums1 = [1,2,3,0,0,0] nums2 = [2,5,6]
初始：
i -> 3 j -> 6 k -> 最后位置
步骤：
| 比较 | 放入 | 数组变成 |
|---|---|---|
| 3 vs 6 | 6 | [1,2,3,0,0,6] |
| 3 vs 5 | 5 | [1,2,3,0,5,6] |
| 3 vs 2 | 3 | [1,2,3,3,5,6] |
| 2 vs 2 | 2 | [1,2,2,3,5,6] |
完成。
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 还有剩余
while (j >= 0) {
nums1[k--] = nums2[j--];
}
}
| 项目 | 复杂度 |
|---|---|
| 时间复杂度 | O(m + n) |
| 空间复杂度 | O(1) |
nums2 为空
直接返回即可，不会进入循环。
nums1 没有有效元素
直接把 nums2 拷贝过去。
仍然能正常处理。
这题是经典基础题，但面试官爱问：
本质考察：
如果改成：
合并两个有序链表？
那就变成经典链表双指针题。
如果改成：
合并 K 个有序数组？
那就需要优先队列（小顶堆）。
本题核心只有一句话：
有空位在后面，就从后面往前填。
这是一个必须秒杀的基础题，属于：
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online