#88

简单

高频

reverse-double-pointer

合并两个有序数组

这是一道围绕数组展开的高频练习。建议先掌握「reverse-double-pointer」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。

数组

题目分析

这道题表面上是在处理「合并两个有序数组」，但先要想清楚题目到底让你返回什么，以及过程中哪些约束必须一直满足。从题型上看，它主要在考数组这些能力。这类题通常依赖两个位置之间的相对移动，关键是先明确每次移动的依据是什么。只有先把题目要求翻译成人话，后面的推荐代码才是在实现思路，而不是直接给答案。

接下来怎么看推荐代码：带着这个理解再看推荐代码时，重点观察这条主线：从两个数组尾部开始比较，把更大的值填到 nums1 的最后一个空位里。

推荐代码

推荐解法：reverse-double-pointer

时间复杂度： O(m+n)

空间复杂度： O(1)

核心思路：从两个数组尾部开始比较，把更大的值填到 nums1 的最后一个空位里。

import java.util.Arrays;

class Solution {

    // 逆向双指针，时间复杂度：O(m+n) 空间复杂度：O(1)
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1, p2 = n - 1;
        int tail = m + n - 1;
        int cur;
        while (p1 >= 0 || p2 >= 0) {
            if (p1 == -1) {
                cur = nums2[p2--];
            } else if (p2 == -1) {
                cur = nums1[p1--];
            } else if (nums1[p1] > nums2[p2]) {
                cur = nums1[p1--];
            } else {
                cur = nums2[p2--];
            }
            nums1[tail--] = cur;
        }
    }

    // 合并后排序。时间复杂度：O((m+n)log(m+n)) 空间复杂度：O(log(m+n))
    public void merge1(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i != n; ++i) {
            nums1[m + i] = nums2[i];
        }
        Arrays.sort(nums1);
    }
}

结构化讲解

面试时怎么讲

开场思路

这题我会用逆向双指针，避免覆盖 nums1 还没处理的值。

核心过程

先让两个数组的有效尾部各有一个指针，再加一个写入尾指针。
每次比较两个尾值，把更大的写到 nums1 末尾。
写入后对应指针左移，直到某一边耗尽。
最后如果 nums2 还有剩余，再整体补到前面。

复杂度总结

时间复杂度 O(m+n)，空间复杂度 O(1)。

面试补一句：这题最关键的不是双指针本身，而是“必须逆向写”。

核心思路

因为 nums1 后面预留了空位，所以不能从前往后合并，否则会覆盖还没处理的值。逆向双指针正好能原地完成合并。

步骤讲解

初始化三个尾指针

分别指向 nums1 有效部分尾部、nums2 尾部和最终填充位置尾部。

为什么这样做：逆向填充需要同时知道两个候选尾值和当前写入位置。

对应代码提示：int i = m - 1, j = n - 1, write = m + n - 1;

每次把更大的尾值写到后面

比较 nums1[i] 和 nums2[j]，把更大的那个写到 nums1[write]。

为什么这样做：后面位置不会再被使用，逆向写入不会覆盖未处理数据。

对应代码提示：nums1[write--] = nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];

如果 nums2 还有剩余，继续补到前面

当 nums1 先用完时，把 nums2 剩余值继续填到 nums1 开头。

为什么这样做：nums1 自身剩余值本来就在正确位置，只有 nums2 需要补齐。

对应代码提示：while (j >= 0) nums1[write--] = nums2[j--];

易错点

从前往后合并

会覆盖 nums1 里还没拿来比较的原始有效元素。

正确理解：必须从尾部开始写回。

认为 nums1 剩余也要单独搬运

当 nums2 耗尽后，nums1 剩余元素已经在正确位置上。

正确理解：只需要额外处理 nums2 剩余部分。

尾指针初始化偏一位

很容易写出越界或漏掉最后一个元素。

正确理解：写入指针必须从 m+n-1 开始。

复杂度与适用判断

时间复杂度：O(m+n)

空间复杂度：O(1)

比其他方案更好在哪里：比额外开新数组再拷回更省空间，也更符合题目原地修改要求。

适用判断：数组尾部有空位，且需要原地合并两个有序序列时，优先考虑逆向双指针。

额外提醒

逆向写入是避免覆盖的唯一关键。

动画演示

如果你还没完全看懂，可以展开动画演示。

reverse-double-pointer动画演示

想看这段解法是怎么一步步运行的，可以展开动画继续观察。

nums1数组值:

m (nums1有效元素数):

nums2数组值:

n (nums2有效元素数):

准备就绪 - 输入数组值和有效元素数量，然后点击开始

动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。