4. 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
解题思路总览
- 完整归并法（暴力合并后取中位）
- 双指针部分归并（只走到中位位置）
- 二分划分法（对较短数组做二分，O(log(min(m,n)))）
- 第 k 小元素法（递归缩减 k，O(log(m+n)))
思路一：完整归并法（暴力）
原理与适用场景：
将两个有序数组整体按归并排序方式合并到一个新数组，再取中位数。时间 O(m+n)，空间 O(m+n)。实现最直观，适合数据规模小或用于验证其它算法正确性。
实现步骤：
- 申请长度 m+n 的临时数组。
- 双指针 i,j 同步遍历，依次写入较小值。
- 追加尚未耗尽数组的剩余部分。
- 根据总长度奇偶返回中位数或两中点平均。
JAVA 代码实现（逐行中文注释）：
public double findMedianSortedArraysMerge(int[] nums1, int[] nums2) { // 入口：暴力完整归并
int m = nums1.length; // 数组1长度
int n = nums2.length; // 数组2长度
int[] merged = new int[m + n]; // 新数组存放合并结果
int i = 0, j = 0, k = 0; // i/j 指向原数组；k 指向合并数组写入位置
while (i < m && j < n) { // 两数组都还有元素
if (nums1[i] <= nums2[j]) { // 选择较小（稳定）
merged[k++] = nums1[i++]; // 复制 nums1[i] 并移动指针
} else { // 否则选择 nums2[j]
merged[k++] = nums2[j++]; // 复制 nums2[j] 并移动指针
}
}
while (i < m) merged[k++] = nums1[i++]; // 复制 nums1 剩余元素
while (j < n) merged[k++] = nums2[j++]; // 复制 nums2 剩余元素
int total = m + n; // 合并后总长度
if ((total & 1) == 1) { // 若总长度为奇数
return merged[total / 2]; // 直接返回中间位置元素
} else { // 若为偶数
return (merged[total / 2 - 1] + merged[total / 2]) / 2.0; // 返回两个中点的平均
}
}
思路二：双指针部分归并
原理与适用场景：
不必完整合并，只需走到中位索引（或两个索引）。遍历过程中记录当前与前一个元素。节省空间为 O(1)，时间仍最坏 O(m+n)。适合中等规模、追求更低常数的场景。
实现步骤：
- 计算总长度 total，确定需要访问的一个或两个目标位置 target1 / target2。
- i,j 指向两数组，循环选择较小元素，模拟归并序列下标 idx++。
- 每次迭代更新 prev=cur, cur=新元素。
- 当 idx == target2 时，根据奇偶返回结果。
JAVA 代码实现：
public double findMedianSortedArraysPartial(int[] nums1, int[] nums2) { // 入口：部分归并到中位
int m = nums1.length, n = nums2.length; // 记录长度
int total = m + n; // 总长度
int target2 = total / 2; // 第二目标位置（奇偶通用）
int target1 = (total % 2 == 0) ? target2 - 1 : target2; // 若偶数需要两个位置
int i = 0, j = 0; // 两个数组的扫描指针
int idx = -1; // 已“取出”的元素在归并序列中的位置
int prev = 0, cur = 0; // prev 保存前一个值，cur 保存当前值
while (i < m || j < n) { // 只要至少一个数组未耗尽
int val; // 当前挑选出的值
if (i < m && (j >= n || nums1[i] <= nums2[j])) { // 选择 nums1 当前元素
val = nums1[i++]; // 取出并前进 i
} else { // 否则选择 nums2 当前元素
val = nums2[j++]; // 取出并前进 j
}
idx++; // 归并位置前进
prev = cur; // 更新前一个值
cur = val; // 设置当前值
if (idx == target2) { // 已达到较大目标位置
if ((total & 1) == 1) { // 若总长度奇数
return cur; // 直接返回当前值
} else { // 若总长度偶数
return (prev + cur) / 2.0; // 两个中位位置求平均
}
}
}
return 0.0; // 理论上不可达
}
思路三：二分划分法（推荐最优）
原理与适用场景：
设在两个数组上各取一条“分割线”，使得左半部分共 (m+n+1)/2 个元素，且 leftMax <= rightMin。只需在较短数组上二分尝试其分割位置 i，同时 j = leftTotal - i 自动确定另一个数组的分割。满足边界条件后即可在 O(1) 时间计算中位数。整体时间 O(log(min(m,n)))，空间 O(1)。适合需要满足题目对数级复杂度要求的主流场景。
实现步骤：
- 若 nums1 长度大于 nums2，交换以保证 nums1 更短。
- 设 leftTotal = (m+n+1)/2，二分 i ∈ [0,m]，对应 j = leftTotal - i。
- 取 nums1LeftMax, nums1RightMin, nums2LeftMax, nums2RightMin（越界用 ±∞）。
- 若 nums1LeftMax > nums2RightMin，说明 i 太大（左侧来自 nums1 的元素多了），hi = i - 1。
- 否则若 nums2LeftMax > nums1RightMin，说明 i 太小，lo = i + 1。
- 否则找到合法划分：奇数总长返回 maxLeft；偶数返回 (maxLeft + minRight)/2。
JAVA 代码实现：
public double findMedianSortedArraysBinary(int[] nums1, int[] nums2) { // 入口：二分划分法
if (nums1.length > nums2.length) { // 保证 nums1 更短，提高二分效率
return findMedianSortedArraysBinary(nums2, nums1); // 若不满足则交换参数
}
int m = nums1.length, n = nums2.length; // 两数组长度
int leftTotal = (m + n + 1) / 2; // 左侧应包含的总元素数（偏向左）
int lo = 0, hi = m; // 在短数组范围内二分
while (lo <= hi) { // 标准二分循环
int i = lo + (hi - lo) / 2; // nums1 左部分取 i 个
int j = leftTotal - i; // nums2 左部分取 j 个
int nums1LeftMax = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1]; // i==0 则左侧无元素 => -∞
int nums1RightMin = (i == m) ? Integer.MAX_VALUE : nums1[i]; // i==m 则右侧无元素 => +∞
int nums2LeftMax = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1]; // 同理处理边界
int nums2RightMin = (j == n) ? Integer.MAX_VALUE : nums2[j]; // 同理处理边界
if (nums1LeftMax > nums2RightMin) { // i 过大，需要左移
hi = i - 1; // 调整上界
} else if (nums2LeftMax > nums1RightMin) { // i 过小，需要右移
lo = i + 1; // 调整下界
} else { // 找到合法划分
int maxLeft = Math.max(nums1LeftMax, nums2LeftMax); // 左侧最大值
if (((m + n) & 1) == 1) { // 若总长度为奇数
return maxLeft; // 直接返回左侧最大
} else { // 若总长度为偶数
int minRight = Math.min(nums1RightMin, nums2RightMin); // 右侧最小值
return (maxLeft + minRight) / 2.0; // 平均得到中位数
}
}
}
return 0.0; // 理论上不可能执行到此
}
思路四：第 k 小元素法（通用递归）
原理与适用场景：
中位数可视为第 k 小（或两次查询）。递归比较两个数组当前第 k/2 小的候选并丢弃较小侧的前 half 个元素，k 随之减少。每轮至少丢弃 k/2 个元素，总复杂度 O(log(m+n))。可扩展到任意 k 查询。
实现步骤：
- 定义 getK(a,i,b,j,k) 返回从 a[i:], b[j:] 合并后的第 k 小。
- 若某数组已耗尽，直接在另一数组取第 k 个。
- 若 k==1，返回两数组首元素较小者。
- half = k/2，计算 a 与 b 对应的比较位置 i+half-1 与 j+half-1，越界视为 +∞。
- 丢弃较小值所在数组的前 half 个元素，递归更新 k。
- 根据奇偶一次或两次调用得到中位数。
JAVA 代码实现：
public double findMedianSortedArraysKth(int[] nums1, int[] nums2) { // 入口：第 k 小模型获得中位数
int m = nums1.length, n = nums2.length; // 记录两数组长度
int total = m + n; // 总元素数
if ((total & 1) == 1) { // 若总长度为奇数
return getKth(nums1, 0, nums2, 0, total / 2 + 1); // 取第 (total/2+1) 小
} else { // 若总长度为偶数
double left = getKth(nums1, 0, nums2, 0, total / 2); // 左侧中位位置
double right = getKth(nums1, 0, nums2, 0, total / 2 + 1); // 右侧中位位置
return (left + right) / 2.0; // 平均得到中位数
}
}
private double getKth(int[] a, int i, int[] b, int j, int k) { // 递归：返回第 k 小
if (i >= a.length) return b[j + k - 1]; // a 用尽 -> 直接从 b 取
if (j >= b.length) return a[i + k - 1]; // b 用尽 -> 直接从 a 取
if (k == 1) return Math.min(a[i], b[j]); // k==1 返回两者较小
int half = k / 2; // 每轮丢弃至少 half 个
int iNew = i + half - 1; // a 的比较索引
int jNew = j + half - 1; // b 的比较索引
int aVal = (iNew >= a.length) ? Integer.MAX_VALUE : a[iNew]; // 越界视作 +∞
int bVal = (jNew >= b.length) ? Integer.MAX_VALUE : b[jNew]; // 越界视作 +∞
if (aVal < bVal) { // a 的前 half 个全都较小
return getKth(a, i + half, b, j, k - half); // 丢弃 a 的 half 个
} else { // 否则丢弃 b 的 half 个
return getKth(a, i, b, j + half, k - half); // 继续递归求解
}
}
补充说明（方法对比）
时间复杂度：
- 完整归并：O(m+n)
- 部分归并：O(m+n)（最坏）
- 二分划分：O(log(min(m,n)))（题目期望首选）
- 第 k 小：O(log(m+n))
空间复杂度： - 完整归并：O(m+n)
- 部分归并：O(1)
- 二分划分：O(1)
- 第 k 小：O(log(m+n)) 递归栈（可改迭代降为 O(1)）
优缺点概述： - 完整归并：实现最简单；空间 & 线性时间较大，不满足对数复杂度目标。
- 部分归并：省空间；仍是线性时间，适合快速验证。
- 二分划分：代码精炼，常量空间，对数时间；需仔细处理边界。
- 第 k 小：通用可复用到任意排名查询；实现略长，有递归栈。
边界情况： - 一数组为空：全部方法（除完整归并外的优化法）均已显式处理或天然兼容。
- 元素全部相同：不影响划分条件判定。
- 长度极端悬殊：二分划分仍只在短数组上二分，性能稳定。
- 溢出风险：仅在偶数平均时涉及两 int 相加（安全）。若值范围接近上限可先转 long。
选择建议：
生产/性能敏感：二分划分；
需要扩展任意 k：第 k 小；
教学 / 调试：部分归并；
快速草稿：完整归并。
至此，四种思路的原理、步骤、完整 Java 逐行注释实现及复杂度比较已全部给出。