在算法面试与前端开发的技术栈中，“寻找两个有序数组的中位数” 是一道极具代表性的经典题目。它不仅考察对数组特性的理解，更考验对时间复杂度优化的思维能力。今天，我们就来拆解这道题的核心逻辑，从暴力解法到最优解，一步步实现从 “能跑” 到 “优雅” 的跨越。
题目回顾
给定两个大小分别为
m 和 n 的有序数组 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)/2=2.5。
暴力解法：合并数组，直接查找
这是最直观的思路，既然两个数组都是有序的，那我们可以先将它们合并成一个新的有序数组，再根据数组长度的奇偶性直接计算中位数。
实现思路
- 双指针遍历两个数组，依次比较当前指针指向的元素，将较小的元素加入新数组，直到其中一个数组遍历完毕。
- 将未遍历完的数组剩余元素直接追加到新数组末尾。
- 判断新数组长度的奇偶性：奇数则取中间元素，偶数则取中间两个元素的平均值。
代码实现（博客通用格式）
javascript
运行
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
// 初始化双指针和合并后的数组
let i = 0, j = 0;
const merged = [];
const m = nums1.length, n = nums2.length;
// 双指针合并有序数组
while (i < m && j < n) {
if (nums1[i] <= nums2[j]) {
merged.push(nums1[i++]);
} else {
merged.push(nums2[j++]);
}
}
// 追加剩余元素
while (i < m) {
merged.push(nums1[i++]);
}
while (j < n) {
merged.push(nums2[j++]);
}
// 计算中位数
const len = merged.length;
if (len % 2 === 1) {
return merged[Math.floor(len / 2)];
} else {
const mid = len / 2;
return (merged[mid - 1] + merged[mid]) / 2;
}
};
优缺点分析
- 优点：逻辑简单，易于理解和实现，适合入门阶段练手。
- 缺点：时间复杂度为 O(m+n)（需要遍历两个数组的所有元素），空间复杂度为 O(m+n)（需要额外存储合并后的数组），不满足题目要求的 O (log (m+n)) 时间复杂度，在数据量较大时性能较差。
最优解法：二分查找，切割数组
要达到 O(log (m+n)) 的时间复杂度，必须利用二分查找的思想。核心思路是：不合并数组，而是通过切割两个数组，将其划分为左右两部分，使得左半部分的所有元素都小于等于右半部分的所有元素，且左右部分的长度差不超过 1。
核心逻辑
- 确保
nums1是较短的数组（减少二分次数，优化性能）。 - 对
nums1进行二分查找，定义切割位置i，根据总长度的奇偶性，计算nums2的切割位置j。 - 切割后，
nums1的左半部分为nums1[0...i-1]，右半部分为nums1[i...m-1]；nums2的左半部分为nums2[0...j-1]，右半部分为nums2[j...n-1]。 - 验证条件：
nums1[i-1] <= nums2[j]且nums2[j-1] <= nums1[i]。满足则说明切割正确；不满足则调整二分查找的范围。 - 根据切割位置计算中位数：
- 总长度为奇数：取左半部分的最大值（即
max(nums1[i-1], nums2[j-1])）。 - 总长度为偶数：取左半部分的最大值和右半部分的最小值的平均值（即
(max(nums1[i-1], nums2[j-1]) + min(nums1[i], nums2[j])) / 2）。
- 总长度为奇数：取左半部分的最大值（即
边界处理
- 当
i=0时，nums1左半部分为空，左半部分最大值为nums2[j-1]。 - 当
i=m时，nums1右半部分为空，右半部分最小值为nums2[j]。 - 同理处理
j=0和j=n的情况。
代码实现（博客通用格式）
javascript
运行
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
// 确保 nums1 是较短的数组，减少二分次数
if (nums1.length > nums2.length) {
[nums1, nums2] = [nums2, nums1];
}
const m = nums1.length;
const n = nums2.length;
let left = 0, right = m; // 二分查找的范围：nums1 的切割位置 [0, m]
while (left <= right) {
// 切割 nums1：左半部分 [0, i-1]，右半部分 [i, m-1]
const i = Math.floor((left + right) / 2);
// 切割 nums2：左半部分 [0, j-1]，右半部分 [j, n-1]
// 保证左右两部分总长度相等（总长度奇数时左半部分多一个）
const j = Math.floor((m + n + 1) / 2) - i;
// 边界值处理：越界时赋值为无穷大/无穷小
const nums1Left = i === 0 ? -Infinity : nums1[i - 1];
const nums1Right = i === m ? Infinity : nums1[i];
const nums2Left = j === 0 ? -Infinity : nums2[j - 1];
const nums2Right = j === n ? Infinity : nums2[j];
// 验证切割条件：左半部分最大值 <= 右半部分最小值
if (nums1Left <= nums2Right && nums2Left <= nums1Right) {
// 总长度为奇数
if ((m + n) % 2 === 1) {
return Math.max(nums1Left, nums2Left);
} else {
// 总长度为偶数
return (Math.max(nums1Left, nums2Left) + Math.min(nums1Right, nums2Right)) / 2;
}
} else if (nums1Left > nums2Right) {
// nums1 左半部分太大，向左切割
right = i - 1;
} else {
// nums2 左半部分太大，向右切割
left = i + 1;
}
}
// 理论上不会执行到此处，仅为了满足函数返回要求
return 0.0;
};
复杂度分析
- 时间复杂度：O (log (min (m,n)))。二分查找的次数取决于较短数组的长度，每一次二分的操作都是常数时间，因此满足题目要求的 O (log (m+n))。
- 空间复杂度：O (1)。仅使用了常数级别的额外空间，无需合并数组。
测试验证
我们用题目中的示例来测试两种解法，确保代码正确性：
javascript
运行
// 测试示例1
console.log(findMedianSortedArrays([1,3], [2])); // 输出 2.0
// 测试示例2
console.log(findMedianSortedArrays([1,2], [3,4])); // 输出 2.5
// 测试示例3：空数组情况
console.log(findMedianSortedArrays([], [1])); // 输出 1.0
console.log(findMedianSortedArrays([3], [-2, -1])); // 输出 -1.0
总结
寻找两个有序数组的中位数这道题，从暴力解法到二分解法，体现了算法优化的核心思想：利用问题特性，减少不必要的计算。
- 暴力解法是基础，适合理解问题本质，但不适合实际应用。
- 二分解法是最优解，通过切割数组和边界验证，将时间复杂度优化到 O (log (m+n))，是面试中的标准解法。
在实际开发中，我们很少会遇到需要处理两个超大有序数组的中位数场景，但这道题所体现的二分查找思想、边界处理能力和算法优化思维，是前端开发和算法学习中非常宝贵的技能。希望这篇文章能帮助你彻底理解这道经典题目，也能让你在算法面试中从容应对！
