合并两个有序数组

题目链接：88. 合并两个有序数组 - 力扣（LeetCode）

难度：简单
标签：数组、双指针

题目描述#

Note

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

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

注意：最终结果应存储在数组 nums1 中。nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。

示例#

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

方案：逆向双指针（原地合并）#

核心思路：如果从前往后合并，我们需要额外的空间来存储 nums1 的原始数据，否则会发生覆盖。但观察题目发现，nums1 的尾部是空的。

使用两个指针 i 和 j 分别指向 nums1 和 nums2 的有效数据末尾。
使用指针 k 指向 nums1 的真正末尾（m + n - 1）。
比较 nums1[i] 和 nums2[j]，将较大的数填入 nums1[k]，并向前移动指针。
这种方式不需要额外空间，且不会覆盖掉还未比较的元素。

源码实现#

1
class Solution {
2
public:
3
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
4
        int i = m - 1;      // nums1 的有效末尾
5
        int j = n - 1;      // nums2 的末尾
6
        int k = m + n - 1;  // nums1 的实际空间末尾
7

8
        // 从后往前填充，避免覆盖原有数据
9
        while (i >= 0 && j >= 0) {
10
            if (nums1[i] > nums2[j]) {
11
                nums1[k--] = nums1[i--];
12
            } else {
13
                nums1[k--] = nums2[j--];
14
            }
15
        }
16

17
        // 如果 nums2 还有剩余，将其全部拷贝到 nums1 前部
18
        // 注意：如果 nums1 还有剩余则不需要处理，因为它们已经在正确的位置上了
19
        while (j >= 0) {
20
            nums1[k--] = nums2[j--];
21
        }
22
    }
23
};

复杂度分析#

时间复杂度： $O(m + n)$ 。其中 $m$ 和 $n$ 分别是两个数组的长度。我们只需扫描两个数组各一次。
空间复杂度： $O(1)$ 。我们直接在 nums1 的预留空间上进行操作，没有使用额外空间。

总结#

逆向思维：很多“数组原地修改”的问题，从后往前考虑往往能避开“覆盖原始数据”的陷阱。
与链表合并的区别：本题与第 21 题（合并有序链表）思路一致，但数组的内存连续性允许我们利用尾部空闲空间进行优化。
细节处理：最后的 while(j >= 0) 非常关键，它处理了 nums2 还有剩余而 nums1 已遍历完的情况。

Tip

“从后往前”是处理原地数组合并的黄金法则。掌握了这个技巧，你就掌握了此类问题的最优解！

音乐

音乐