021-寻找两个正序数组的中位数 (Median of Two Sorted Arrays)
LeetCode 第21题 - 寻找两个正序数组的中位数的详细题解，包含二分查找算法和JavaScript实现
题目描述
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数。
算法的时间复杂度应该为 O(log (m+n))。
示例
示例 1：
输入: nums1 = [1,3], nums2 = [2]
输出: 2.00000
解释: 合并数组 = [1,2,3] ，中位数 2示例 2：
输入: nums1 = [1,2], nums2 = [3,4]
输出: 2.50000
解释: 合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5示例 3：
输入: nums1 = [0,0], nums2 = [0,0]
输出: 0.00000示例 4：
输入: nums1 = [], nums2 = [1]
输出: 1.00000示例 5：
输入: nums1 = [2], nums2 = []
输出: 2.00000解题思路
二分查找法（推荐）
这道题要求时间复杂度为 O(log(m+n))，因此不能使用合并排序的方法。我们可以使用二分查找的思想来解决。
核心思想：
- 将两个数组分成左右两部分，使得左边部分的所有元素都小于右边部分
- 左边部分的元素个数等于右边部分的元素个数（或左边多一个）
- 中位数就是左边部分的最大值和右边部分的最小值的平均值
算法步骤：
- 确保 nums1 是较短的数组
- 在较短的数组中进行二分查找，找到合适的分割点
- 根据分割点计算另一个数组的分割点
- 检查分割是否满足条件，如果满足则计算中位数
- 根据比较结果调整二分查找的范围
JavaScript 解决方案
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
const findMedianSortedArrays = function(nums1, nums2) {
// 确保 nums1 是较短的数组
if (nums1.length > nums2.length) {
[nums1, nums2] = [nums2, nums1];
}
const m = nums1.length;
const n = nums2.length;
const leftTotal = Math.floor((m + n + 1) / 2);
// 在较短的数组中进行二分查找
let left = 0;
let right = m;
while (left <= right) {
// nums1 的分割点
const i = Math.floor((left + right) / 2);
// nums2 的分割点
const j = leftTotal - i;
// nums1 左边部分的最大值
const nums1LeftMax = i === 0 ? -Infinity : nums1[i - 1];
// nums1 右边部分的最小值
const nums1RightMin = i === m ? Infinity : nums1[i];
// nums2 左边部分的最大值
const nums2LeftMax = j === 0 ? -Infinity : nums2[j - 1];
// nums2 右边部分的最小值
const nums2RightMin = j === n ? Infinity : nums2[j];
// 检查分割是否满足条件
if (nums1LeftMax <= nums2RightMin && nums2LeftMax <= nums1RightMin) {
// 找到正确的分割点
if ((m + n) % 2 === 1) {
// 奇数长度，中位数是左边部分的最大值
return Math.max(nums1LeftMax, nums2LeftMax);
} else {
// 偶数长度，中位数是左边部分最大值和右边部分最小值的平均值
return (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2;
}
} else if (nums1LeftMax > nums2RightMin) {
// nums1 左边部分太大，需要向左移动
right = i - 1;
} else {
// nums1 左边部分太小，需要向右移动
left = i + 1;
}
}
// 正常情况下不会到达这里
return 0;
};复杂度分析
时间复杂度：O(log(min(m,n)))
- 二分查找在较短的数组上进行
- 每次查找的时间复杂度为 O(1)
- 总共进行 O(log(min(m,n))) 次查找
空间复杂度：O(1)
- 只使用了常数额外空间
测试用例
// 测试函数
function testFindMedianSortedArrays() {
const testCases = [
{ nums1: [1,3], nums2: [2], expected: 2.0 },
{ nums1: [1,2], nums2: [3,4], expected: 2.5 },
{ nums1: [0,0], nums2: [0,0], expected: 0.0 },
{ nums1: [], nums2: [1], expected: 1.0 },
{ nums1: [2], nums2: [], expected: 2.0 },
{ nums1: [1,2,3,4,5], nums2: [6,7,8,9,10], expected: 5.5 },
{ nums1: [1,2,3,4,5], nums2: [6,7,8,9], expected: 5.0 },
{ nums1: [1,3,5,7,9], nums2: [2,4,6,8,10], expected: 5.5 },
{ nums1: [1,2,3], nums2: [4,5,6,7,8,9], expected: 5.0 },
{ nums1: [1], nums2: [2,3,4,5,6], expected: 3.5 }
];
testCases.forEach((testCase, index) => {
const result = findMedianSortedArrays(testCase.nums1, testCase.nums2);
const passed = Math.abs(result - testCase.expected) < 0.00001;
console.log(`测试用例 ${index + 1}: ${passed ? '✅' : '❌'}`);
console.log(`输入: nums1 = [${testCase.nums1}], nums2 = [${testCase.nums2}]`);
console.log(`期望: ${testCase.expected}`);
console.log(`实际: ${result}`);
console.log('---');
});
}
// 运行测试
testFindMedianSortedArrays();关键点总结
- 数组交换：确保在较短的数组上进行二分查找，提高效率
- 分割点计算：根据总长度计算左右两部分应该包含的元素个数
- 边界处理：使用 Infinity 和 -Infinity 处理数组边界情况
- 条件检查：确保左边部分的所有元素都小于右边部分
- 奇偶处理：根据总长度的奇偶性计算不同的中位数
总结
这道题是二分查找的高级应用，考察了对算法复杂度的理解和二分查找的灵活运用。
考察重点：
- 二分查找算法的应用
- 时间复杂度分析
- 边界条件的处理
- 数学思维的运用
- 代码的严谨性
这道题是很多面试中的经典题目，掌握二分查找的思想对于解决类似问题很有帮助。在实际面试中，建议先提出合并排序的解法，然后优化到二分查找解法。