Median of Two Sorted Arrays 是 LeetCode 上非常经典的一道题。
题目要求给定两个已经按升序排列的整数数组 nums1 和 ，请你找出这两个数组合并后的中位数，并返回这个中位数。
很多人看到这道题时，第一反应会想到“先合并，再取中位数”。 而这份代码实际上就是基于这个思路做了一个优化版的模拟合并：
-
不真正创建完整合并数组
-
只在遍历过程中记录中位数附近的两个值
-
当遍历到中间位置时直接返回结果
这种写法虽然没有达到题目进阶要求的 O(log(m+n))，但思路清晰、实现稳定，非常适合作为理解这道题的第一步。
题目示例
输入：nums1 = [1,3], nums2 = [2]
输出：2.0
合并后的有序数组为：
[1,2,3]
中位数就是 2.0。
再看一个例子：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.5
合并后的有序数组为：
[1,2,3,4]
因为总长度为偶数，中位数就是中间两个数 (2 + 3) / 2 = 2.5。
解题思路
这段代码的核心思想其实很像“归并排序”中的合并过程：
-
使用两个指针分别指向两个数组当前未处理的位置
-
每次取两个数组中较小的那个数
-
按照从小到大的顺序不断取数
-
由于中位数只和中间位置有关，所以我们不需要真的把所有元素都存下来
-
只要记录当前取到的数，以及上一个取到的数，就可以在遍历到中间位置时算出答案
这样可以避免额外创建一个新数组，空间复杂度保持在 O(1)。
Java 代码（带注释）
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// n 和 m 分别表示两个数组的长度
int n = nums1.length;
int m = nums2.length;
// flag 用来判断总长度是否为偶数
// 如果为 true，说明最后需要返回中间两个数的平均值
boolean flag = ((m + n) % 2) == 0;
// point1 和 point2 分别是两个数组的遍历指针
int point1 = 0, point2 = 0;
// remNum1 表示当前取到的数
// remNum2 表示上一次取到的数
// 这两个变量用于最后计算中位数
int remNum1 = 0, remNum2 = 0;
// 只需要遍历到总长度的一半位置即可
for (int i = 0; i <= (n + m) / 2; i++) {
// 在更新当前值之前，先把当前值保存到 remNum2
remNum2 = remNum1;
// 如果 nums1 还没遍历完，并且满足以下任一条件：
// 1. nums2 已经遍历完
// 2. nums1 当前值小于 nums2 当前值
// 那么这一次就取 nums1[point1]
if (point1 < n && (point2 >= m || nums1[point1] < nums2[point2])) {
remNum1 = nums1[point1++];
} else {
// 否则取 nums2[point2]
remNum1 = nums2[point2++];
}
}
// 如果总长度为偶数，中位数是中间两个数的平均值
if (flag) {
return (remNum1 + remNum2) / 2.0;
} else {
// 如果总长度为奇数，中位数就是当前这个数
return remNum1 * 1.0;
}
}
}
变量含义拆解
为了更容易理解这段代码，可以先把几个关键变量搞清楚。
point1 和 point2
这两个变量分别表示：
-
point1：当前遍历到nums1的哪个位置 -
point2：当前遍历到nums2的哪个位置
它们的作用就像两个有序队列的指针。
remNum1 和 remNum2
这两个变量是整段代码里最关键的部分：
-
remNum1：当前取出的元素 -
remNum2：上一个取出的元素
为什么要保存两个数？
因为当总长度是偶数时，中位数需要用到中间两个数的平均值。 所以必须同时保留当前值和前一个值。
flag
boolean flag = ((m + n) % 2) == 0;
这个变量用来判断两个数组合并后的总长度是否为偶数：
-
偶数：返回中间两个数的平均值
-
奇数：返回中间那个数
执行过程演示
以这组输入为例：
nums1 = [1,2]
nums2 = [3,4]
总长度为 4，属于偶数情况。
我们只需要遍历到下标 4 / 2 = 2 这个位置。
第 1 次循环
当前指针：
-
point1 = 0 -
point2 = 0
比较：
-
nums1[0] = 1 -
nums2[0] = 3
较小的是 1，所以：
remNum2 = 0
remNum1 = 1
第 2 次循环
比较：
-
nums1[1] = 2 -
nums2[0] = 3
较小的是 2，所以：
remNum2 = 1
remNum1 = 2
第 3 次循环
此时 nums1 已经遍历完，接下来只能取 nums2 的元素。
所以：
remNum2 = 2
remNum1 = 3
遍历结束后：
-
remNum2 = 2 -
remNum1 = 3
因为总长度是偶数，所以中位数为：
(2 + 3) / 2.0 = 2.5
为什么循环只到 (n + m) / 2
因为我们并不需要真的把整个合并数组都构造出来。
中位数只和中间位置有关：
-
如果总长度是奇数，只需要第
((n + m) / 2)个元素 -
如果总长度是偶数，只需要第
((n + m) / 2)个元素和它前一个元素
所以遍历到中间位置就够了，后面的元素不影响答案。
代码中的细节说明
为什么判断条件是这样写的？
if (point1 < n && (point2 >= m || nums1[point1] < nums2[point2]))
这句条件可以拆成两层理解。
第一层：
point1 < n
表示 nums1 还没有遍历完。
第二层：
point2 >= m || nums1[point1] < nums2[point2]
表示满足以下任意一种情况：
-
nums2已经遍历完了，那只能从nums1里取 -
nums1[point1]比nums2[point2]更小，那也应该取nums1
否则，就从 nums2 里取值。
为什么最后要写 / 2.0 和 * 1.0
因为题目返回值类型是 double。
如果写成：
(remNum1 + remNum2) / 2
那么在 Java 中会进行整数除法，结果可能出错。
所以要写成：
(remNum1 + remNum2) / 2.0
这样才能得到正确的小数结果。
同理：
return remNum1 * 1.0;
也是为了把结果转换成 double 类型。
复杂度分析
时间复杂度
O(m + n)
虽然代码没有遍历完整个数组，但最坏情况下仍然要扫描到中间位置，数量级仍然是 O(m + n)。
更准确一点，也可以写成：
O((m + n) / 2)
但在复杂度表示中常数会被省略，所以最终写作 O(m + n)。
空间复杂度
O(1)
因为整个过程中只使用了若干个变量，没有额外创建新的数组或集合。
这道题的特点
这段代码的优点很明显：
-
思路自然，容易理解
-
不需要额外数组
-
比先完整合并再取中位数更节省空间
-
很适合在面试或刷题初期快速写出正确答案
但也要注意一点：
这道题的进阶要求是时间复杂度为 O(log(m+n))，而当前这种写法还没有达到那个标准。
所以这份代码更适合当作：
这道题的基础解法 / 过渡解法
当你把这个过程理解清楚以后，再去学习二分解法会更容易。
总结
这道题本质上是在两个有序数组中，模拟合并的过程，然后找到中间位置对应的值。
整段代码最值得学习的地方有两个：
-
不真正创建合并数组，而是边遍历边记录答案
-
用
remNum1和remNum2保存中位数附近的关键元素
如果你刚开始刷这道题，我很建议先把这种写法彻底理解透。
因为它能帮助你清楚地知道：
-
中位数到底取哪个位置
-
奇数长度和偶数长度有什么区别
-
为什么只遍历到中间位置就够了
这些问题想明白之后，再去看更高阶的二分做法，理解成本会低很多。
适合直接发布的结尾
对于这道题，我觉得比较合适的学习顺序是：
-
先理解合并两个有序数组的过程
-
再理解为什么中位数只和中间位置有关
-
接着掌握这种
O(m+n)的模拟写法 -
最后再挑战
O(log(m+n))的二分解法
