4. 寻找两个正序数组的中位数#
今天我们要挑战一道 LeetCode 难度系数最高的题目之一 - LeetCode 4「寻找两个正序数组的中位数」。这道题不仅考察我们对二分查找的理解，更要求我们具备深入的数学思维。让我们一起攻克这个难题！
📚 从生活场景切入#
想象你是一位体育老师，手里有两份不同班级的体测成绩单，都已经按照分数排序。现在你需要找出这两个班级所有同学成绩的中间水平。直观的做法是把两个成绩单合并后重新排序，但这样效率太低。其实我们可以用更聪明的方法，这就是今天要讨论的问题。
问题描述#
题目目标#
给定两个大小分别为 m 和 n 的正序数组 nums1 和 nums2 ，请你找出并返回这两个正序数组的中位数。题目要求算法的时间复杂度为 O(log(m + n))。
示例 1#
输入： nums1 = [1,3], nums2 = [2]
输出： 2.00000
说明： 合并后为 [1,2,3]，中位数为 2
💡 问题解析#
题目要求： 给定两个有序数组 nums1 和 nums2，要求找出这两个数组的中位数。要求算法的时间复杂度为 O(log(m+n))。
示例：
// 示例1：总长度为奇数
// 输入：nums1 = [1,3], nums2 = [2]
// 输出：2.0
// 解释：合并后为 [1,2,3]，中位数是中间那个数 2
// 示例2：总长度为偶数
// 输入：nums1 = [1,2], nums2 = [3,4]
// 输出：2.5
// 解释：合并后为 [1,2,3,4]，中位数是中间两个数 (2 和 3) 的平均值🤔 思路发展历程#
1. 直观思路（不符合要求）#
最简单的方法是合并两个数组后找中位数，但时间复杂度是 O(m+n)，不满足题目要求。
2. 优化思路#
我们可以转化思路：不需要真正合并数组，只需要找到第 (m+n)/2 小的元素（或者在偶数情况下找第 (m+n)/2 和 (m+n)/2+1 小的元素）。这启发我们使用二分查找来定位这个位置。
🚀 优雅的解决方案#
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// 预处理：始终让 nums1 成为较短数组，
// 这样二分区间更小，逻辑也更稳定
if (nums1.length > nums2.length) {
int[] temp = nums1; // 临时保存 nums1
nums1 = nums2;
nums2 = temp;
}
int m = nums1.length; // 较短数组长度
int n = nums2.length; // 较长数组长度
// 在 nums1 的“切分位置区间” [0, m] 上做二分
// 注意：切分位置可以在元素之间，所以范围是 0 到 m（包含两端）
int left = 0; // 二分左边界（切分位置）
int right = m; // 二分右边界（切分位置）
// 目标：找到切分 i 和 j，使得左半部分元素都 <= 右半部分元素
while (left <= right) {
int i = (left + right) / 2; // nums1 的切分点：左侧取 i 个元素
int j = (m + n + 1) / 2 - i; // nums2 的切分点：保证左半部分总数固定
// 取出四个关键边界值：
// maxLeft1/minRight1 分别是 nums1 切分线左侧最大值和右侧最小值
// maxLeft2/minRight2 分别是 nums2 切分线左侧最大值和右侧最小值
// 当切分在最边缘时，用 ±∞（这里用整型最小/最大值）作为哨兵避免越界
double maxLeft1 = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
double minRight1 = (i == m) ? Integer.MAX_VALUE : nums1[i];
double maxLeft2 = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
double minRight2 = (j == n) ? Integer.MAX_VALUE : nums2[j];
// 判断切分是否有效：左侧最大值都不大于右侧最小值
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
// 切分有效后，按总长度奇偶性计算中位数
if ((m + n) % 2 == 0) {
// 偶数长度：中位数是“左半最大值”和“右半最小值”的平均
return (Math.max(maxLeft1, maxLeft2) +
Math.min(minRight1, minRight2)) / 2.0;
} else {
// 奇数长度：中位数就是左半部分的最大值
return Math.max(maxLeft1, maxLeft2);
}
}
// 若 maxLeft1 过大，说明 i 取多了，应向左收缩
else if (maxLeft1 > minRight2) {
right = i - 1;
}
else {
// 否则说明 i 取少了，应向右扩展
left = i + 1;
}
}
// 正常输入一定会在循环中返回，这里是防御式异常
throw new IllegalArgumentException("输入数组不合法");
}
}📝 代码详解#
让我们深入理解这个解决方案的精妙之处：
1. 核心思想#
我们要找的是一个位置，将两个数组分别分成左右两部分，使得：
- 左半部分的元素都小于右半部分
- 左半部分的元素个数等于右半部分（或比右半部分多1个）
2. 关键步骤解析#
A. 预处理
- 确保 nums1 是较短的数组，这样可以减少搜索范围
- 计算两个数组的总长度，确定中位数的位置
B. 二分查找过程
- 在较短的数组 nums1 中寻找分割线位置 i
- 根据 i 计算 nums2 中的分割线位置 j
- 比较分割线两侧的元素大小关系
C. 边界处理
- 使用 Integer.MIN_VALUE 和 Integer.MAX_VALUE 处理边界情况
- 分别处理总长度为奇数和偶数的情况
🎯 易错点剖析#
-
数组长度处理
- 必须确保在较短的数组上进行二分查找
- 正确处理奇偶数长度的情况
-
边界条件
- 分割线在数组边缘时的处理
- 两个数组长度差距较大时的情况
-
二分查找的条件
- 正确判断分割线是否合适
- 准确调整搜索范围
💡 举一反三#
这道题的思路可以扩展到其他场景：
-
找第k小的数
- 可以用类似的二分思想
-
合并有序数组
- 理解分割线的概念有助于优化合并过程
-
数据流的中位数
- 类似的思想可以应用到动态数据中
🎨 图解算法#
为了更好地理解这个算法，让我们通过可视化来看看它是如何工作的：
<svg viewBox="0 0 800 400" xmlns="http://www.w3.org/2000/svg">
<!-- 背景 -->
<rect width="800" height="400" fill="#f8f9fa"/>
<!-- 第一个数组 -->
<g transform="translate(50,100)">
<text x="0" y="-20" font-size="16" fill="#1976d2">nums1:</text>
<rect width="500" height="50" fill="none" stroke="#1976d2" stroke-width="2"/>
<!-- 数组元素 -->
<g font-size="14">
<text x="50" y="30" text-anchor="middle">1</text>
<text x="150" y="30" text-anchor="middle">3</text>
<text x="250" y="30" text-anchor="middle">5</text>
<text x="350" y="30" text-anchor="middle">7</text>
<text x="450" y="30" text-anchor="middle">9</text>
</g>
<!-- 分割线 -->
<line x1="200" y1="0" x2="200" y2="50" stroke="#e91e63" stroke-width="2" stroke-dasharray="5,5"/>
<text x="200" y="-10" text-anchor="middle" fill="#e91e63">分割线1</text>
</g>
<!-- 第二个数组 -->
<g transform="translate(50,200)">
<text x="0" y="-20" font-size="16" fill="#388e3c">nums2:</text>
<rect width="500" height="50" fill="none" stroke="#388e3c" stroke-width="2"/>
<!-- 数组元素 -->
<g font-size="14">
<text x="50" y="30" text-anchor="middle">2</text>
<text x="150" y="30" text-anchor="middle">4</text>
<text x="250" y="30" text-anchor="middle">6</text>
<text x="350" y="30" text-anchor="middle">8</text>
<text x="450" y="30" text-anchor="middle">10</text>
</g>
<!-- 分割线 -->
<line x1="300" y1="0" x2="300" y2="50" stroke="#e91e63" stroke-width="2" stroke-dasharray="5,5"/>
<text x="300" y="-10" text-anchor="middle" fill="#e91e63">分割线2</text>
</g>
<!-- 说明文字 -->
<g transform="translate(50,300)">
<text x="0" y="20" font-size="14">左半部分最大值: max(3,6)</text>
<text x="0" y="40" font-size="14">右半部分最小值: min(5,8)</text>
<text x="0" y="60" font-size="14">中位数 = (6 + 5) / 2 = 5.5</text>
</g>
<!-- 箭头 -->
<defs>
<marker id="arrowhead" markerWidth="10" markerHeight="7"
refX="9" refY="3.5" orient="auto">
<polygon points="0 0, 10 3.5, 0 7" fill="#666"/>
</marker>
</defs>
</svg>
🌟 面试技巧#
-
思路表达
- 先说明暴力解法的局限
- 解释为什么需要用二分查找
- 清晰描述如何找到分割线
-
复杂度分析
- 解释为什么时间复杂度是 O(log(min(m,n)))
- 说明空间复杂度是 O(1)
-
代码优化
- 展示对边界情况的处理
- 说明如何使代码更简洁高效
这道题是 LeetCode 难度最高的题目之一，但通过我们的详细讲解，相信大家已经理解了它的核心思想。记住，解决复杂问题的关键在于：将大问题拆分成小问题，找到突破口，然后逐步优化解决方案。如果你对这个题目还有任何疑问，欢迎在评论区讨论！