LeetCode 4. 寻找两个正序数组的中位数
LeetCode 4. 寻找两个正序数组的中位数
标签
- 平台：LeetCode
- 难度：困难
- 数据结构：数组
- 算法：二分查找、双指针、模拟
- 解题模式：左右指针、哨兵节点
一、题目概述
给定两个正序数组，求它们合并后的中位数。当前源码提供了两种实现：findMedianSortedArrays 使用二分切割，满足更优复杂度；mergeSortedArrays 先合并数组，再计算中位数，便于理解。
二、解题思路
二分切割法始终在较短数组上二分。目标是找到一条切割线，使两个数组切割后左半部分元素数量等于中位数左侧需要的数量，并且左半部分所有元素都小于等于右半部分所有元素。
为避免切割线位于数组边界时越界，代码使用 Integer.MIN_VALUE 和 Integer.MAX_VALUE 作为边界哨兵。找到合法切割后，如果总长度为奇数，中位数是左半部分最大值；如果总长度为偶数，中位数是左半最大值和右半最小值的平均值。
三、执行过程
- 校验两个数组不能为
null，且不能同时为空。 - 如果
nums1比nums2长，交换参数，保证在短数组上二分。 - 计算左半部分需要的元素数量
leftPartSize。 - 在短数组切割位置
[0, shortLength]上二分。 - 根据短数组切割位置推导长数组切割位置。
- 取四个边界值：短左最大、短右最小、长左最大、长右最小。
- 如果满足合法切割条件，直接计算中位数。
- 否则根据边界大小调整二分区间。
合并数组法则使用两个指针按顺序合并两个正序数组，再根据总长度奇偶返回中位数。
四、代码实现
public class LeetCode0004MedianOfTwoSortedArrays {
public double findMedianSortedArrays(int[] nums1, int[] nums2) { if (nums1 == null || nums2 == null) { throw new IllegalArgumentException("输入数组不能为 null"); } if (nums1.length == 0 && nums2.length == 0) { throw new IllegalArgumentException("两个数组不能同时为空"); }
if (nums1.length > nums2.length) { return findMedianSortedArrays(nums2, nums1); }
int[] shortArray = nums1; int[] longArray = nums2; int shortLength = shortArray.length; int longLength = longArray.length; int totalLength = shortLength + longLength; int leftPartSize = (totalLength + 1) / 2;
int left = 0; int right = shortLength;
while (left <= right) { int shortCut = left + (right - left) / 2; int longCut = leftPartSize - shortCut;
int shortLeftMax = shortCut == 0 ? Integer.MIN_VALUE : shortArray[shortCut - 1]; int shortRightMin = shortCut == shortLength ? Integer.MAX_VALUE : shortArray[shortCut]; int longLeftMax = longCut == 0 ? Integer.MIN_VALUE : longArray[longCut - 1]; int longRightMin = longCut == longLength ? Integer.MAX_VALUE : longArray[longCut];
if (shortLeftMax <= longRightMin && longLeftMax <= shortRightMin) { int leftMax = Math.max(shortLeftMax, longLeftMax); if ((totalLength & 1) == 1) { return leftMax; }
int rightMin = Math.min(shortRightMin, longRightMin); return ((double) leftMax + (double) rightMin) / 2.0; }
if (shortLeftMax > longRightMin) { right = shortCut - 1; } else { left = shortCut + 1; } }
throw new IllegalArgumentException("输入数组必须是正序数组"); }
public double mergeSortedArrays(int[] nums1, int[] nums2) { if (nums1 == null || nums2 == null) { throw new IllegalArgumentException("输入数组不能为 null"); } if (nums1.length == 0 && nums2.length == 0) { throw new IllegalArgumentException("两个数组不能同时为空"); }
int totalLength = nums1.length + nums2.length; int[] merged = new int[totalLength];
int index1 = 0; int index2 = 0; int mergedIndex = 0;
while (index1 < nums1.length && index2 < nums2.length) { if (nums1[index1] <= nums2[index2]) { merged[mergedIndex] = nums1[index1]; index1++; } else { merged[mergedIndex] = nums2[index2]; index2++; } mergedIndex++; }
while (index1 < nums1.length) { merged[mergedIndex] = nums1[index1]; index1++; mergedIndex++; }
while (index2 < nums2.length) { merged[mergedIndex] = nums2[index2]; index2++; mergedIndex++; }
int mid = totalLength / 2; if ((totalLength & 1) == 1) { return merged[mid]; }
return ((double) merged[mid - 1] + (double) merged[mid]) / 2.0; }}五、关键代码说明
leftPartSize：切割后左半部分应该包含的元素数量。shortCut、longCut：两个数组的切割位置。Integer.MIN_VALUE、Integer.MAX_VALUE：用于处理切割线在数组边界时的哨兵值。- 合法切割条件是
shortLeftMax <= longRightMin && longLeftMax <= shortRightMin。 - 偶数长度时先转成
double再相加，避免int溢出。
六、复杂度分析
- 二分切割法时间复杂度：
O(log(min(m, n)))，只在较短数组上二分。 - 二分切割法空间复杂度：
O(1)，只使用常量变量。 - 合并数组法时间复杂度：
O(m + n)，需要合并两个数组。 - 合并数组法空间复杂度：
O(m + n)，需要额外的合并数组。
七、注意事项
- 当前实现要求输入数组不能为
null，也不能同时为空。 - 二分切割法依赖两个输入数组已经按正序排列。
- 切割线在数组头尾时必须使用哨兵值，否则容易数组越界。
- 计算偶数长度中位数时要避免两个极值相加导致整数溢出。
八、面试知识点：二分切割与中位数
1. 为什么这题不能只会合并数组？
合并数组法很直观：把两个有序数组合并成一个有序数组，然后取中位数。当前源码也保留了 mergeSortedArrays，方便理解中位数定义。
但 LeetCode 原题通常要求时间复杂度达到 O(log(m + n))。完整合并需要 O(m + n) 时间和 O(m + n) 空间，不满足更优要求。因此面试重点通常是二分切割法。
2. 中位数的本质是什么？
中位数可以理解为：把所有元素分成左右两部分，并且满足：
左半部分元素数量 == 右半部分元素数量，或左半部分多一个左半部分最大值 <= 右半部分最小值如果总长度是奇数，中位数是左半部分最大值；如果总长度是偶数，中位数是左半部分最大值和右半部分最小值的平均值。
3. 什么是二分切割？
二分切割不是直接二分答案，而是二分“短数组的切割位置”。
假设短数组切 shortCut 个元素到左边，那么长数组左边需要放：
longCut = leftPartSize - shortCut;这样可以保证左右两边的元素数量满足中位数要求。接下来只要判断切割线附近的四个边界值是否有序即可。
4. 为什么一定要在短数组上二分？
在短数组上二分有两个好处：
- 时间复杂度是
O(log(min(m, n)))； - 更容易保证另一个数组的切割位置合法。
当前实现一开始判断：
if (nums1.length > nums2.length) { return findMedianSortedArrays(nums2, nums1);}这一步就是为了始终在较短数组上做二分。
5. 四个边界值分别表示什么？
二分切割时，需要关注：
shortLeftMax：短数组切割线左边最大值；shortRightMin：短数组切割线右边最小值；longLeftMax：长数组切割线左边最大值；longRightMin：长数组切割线右边最小值。
合法切割条件是：
shortLeftMax <= longRightMin && longLeftMax <= shortRightMin满足这个条件，说明左半部分所有元素都小于等于右半部分所有元素。
6. 为什么需要哨兵值？
切割线可能在数组最左边或最右边。
例如短数组为空，或者切割位置为 0，左边没有元素；如果切割位置等于数组长度，右边没有元素。为了避免数组越界，当前实现使用：
Integer.MIN_VALUEInteger.MAX_VALUE作为边界哨兵。
它们的含义是：
- 左边没有元素时，左侧最大值当作负无穷；
- 右边没有元素时，右侧最小值当作正无穷。
7. 二分区间怎么移动？
如果：
shortLeftMax > longRightMin说明短数组左边选多了，shortCut 太靠右，需要左移。
否则说明短数组左边选少了，shortCut 太靠左，需要右移。
这就是当前代码中：
if (shortLeftMax > longRightMin) { right = shortCut - 1;} else { left = shortCut + 1;}8. 为什么求平均值前要转 double？
偶数长度时，中位数是两个数的平均值。
如果直接写：
(leftMax + rightMin) / 2.0leftMax + rightMin 会先按 int 相加，极端情况下可能已经溢出。
当前实现写成：
((double) leftMax + (double) rightMin) / 2.0先转成 double 再相加，可以避免 int 溢出。
9. 这题常见面试追问
- 为什么不是二分两个数组，而是只二分短数组？
leftPartSize = (totalLength + 1) / 2为什么要加1？- 数组为空时怎么处理？
- 总长度奇偶如何分别处理？
- 哨兵值会不会影响答案？
- 输入数组不是有序数组怎么办？
- 合并数组法和二分切割法复杂度分别是多少？
其中 leftPartSize 加 1 是为了在总长度为奇数时，让左半部分多一个元素，便于直接返回左半部分最大值。
10. 回到本题，面试时怎么回答？
可以这样组织回答：
这道题如果直接合并两个有序数组，时间复杂度是
O(m + n)，但更优做法是二分切割。中位数的本质是把合并后的有序序列分成左右两部分，并保证左边最大值小于等于右边最小值。我始终在较短数组上二分切割位置，再根据左半部分总元素数量推导长数组的切割位置。每次只需要比较切割线附近的四个值：短左最大、短右最小、长左最大、长右最小。如果满足
shortLeftMax <= longRightMin && longLeftMax <= shortRightMin，就找到了合法切割。奇数长度返回左半最大值，偶数长度返回左半最大值和右半最小值的平均值。时间复杂度是O(log(min(m, n)))，空间复杂度是O(1)。
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！