当前位置：首页 > ds >正文

LeetCode 4：寻找两个正序数组的中位数

ds 2025/7/31 7:45:20

LeetCode 4：寻找两个正序数组的中位数

在这里插入图片描述

问题定义与核心挑战

给定两个有序（升序）数组 nums1 和 nums2，要求找到它们的中位数，且算法时间复杂度为 O(log(m+n))（m 和 n 分别是两个数组的长度）。

中位数定义：

若合并后数组长度为奇数，中位数是中间位置的元素（如 [1,2,3] 的中位数是 2）。
若合并后数组长度为偶数，中位数是中间两个元素的平均值（如 [1,2,3,4] 的中位数是 (2+3)/2=2.5）。

常规方法的不足

若直接合并两个数组（时间复杂度 O(m+n)），虽能解决问题，但无法满足题目对时间复杂度的严格要求（O(log(m+n))）。因此，必须利用数组有序的特性，通过 二分查找 避免完全合并。

核心思路：二分法定位分割点

中位数的本质是将合并后的数组划分为左右两部分，使得：

左边所有元素 ≤ 右边所有元素；
左边元素个数 ≥ 右边（奇数长度时左边多一个）。

对于两个有序数组，我们可以通过二分查找分割点，将 nums1 和 nums2 分别划分为左右两部分，使得：

nums1 的左半部分 + nums2 的左半部分 ≤ nums1 的右半部分 + nums2 的右半部分；
左半部分总元素数为 (m+n+1)//2（向上取整，保证奇数长度时左边多一个）。

算法步骤详解

步骤 1：统一数组长度（优化二分范围）

为了减少二分查找的范围，确保 nums1 是较短的数组（若 nums1 更长，则交换 nums1 和 nums2）。这样，二分查找仅需在较短数组上进行，降低时间复杂度。

int m = nums1.length, n = nums2.length;
if (m > n) {// 交换数组，确保 nums1 是较短的int[] temp = nums1;nums1 = nums2;nums2 = temp;m = nums1.length;n = nums2.length;
}

步骤 2：二分查找分割点

在 nums1 中二分查找分割点 i，并计算 nums2 的对应分割点 j：

i 表示 nums1 左半部分的元素个数（范围：0 ≤ i ≤ m）；
j = (m + n + 1) // 2 - i，保证左半部分总元素数为 (m+n+1)//2（向上取整）。

int left = 0, right = m;
while (left < right) {// 向上取整，避免死循环（如 left=1, right=2 时，mid=2）int mid = (left + right + 1) / 2; int j = (m + n + 1) / 2 - mid;if (nums1[mid-1] > nums2[j]) {// i 太大，左移右边界right = mid - 1;} else {// i 太小，右移左边界left = mid;}
}
int i = left;
int j = (m + n + 1) / 2 - i;

步骤 3：处理边界值（分割点越界）

分割点 i 或 j 可能为 0（左半部分为空）或等于数组长度（右半部分为空），需用极值（-∞ 或 +∞）处理：

// nums1 左半部分的最大值（i=0 时，左半部分为空，设为 -∞）
double nums1_left = (i == 0) ? Integer.MIN_VALUE : nums1[i-1];
// nums1 右半部分的最小值（i=m 时，右半部分为空，设为 +∞）
double nums1_right = (i == m) ? Integer.MAX_VALUE : nums1[i];
// nums2 左半部分的最大值（j=0 时，左半部分为空，设为 -∞）
double nums2_left = (j == 0) ? Integer.MIN_VALUE : nums2[j-1];
// nums2 右半部分的最小值（j=n 时，右半部分为空，设为 +∞）
double nums2_right = (j == n) ? Integer.MAX_VALUE : nums2[j];

步骤 4：计算中位数

根据合并后数组的长度（m+n）的奇偶性，计算中位数：

奇数：左半部分最大值（max(nums1_left, nums2_left)）；
偶数：左半部分最大值与右半部分最小值的平均值（(max(...) + min(...)) / 2）。

if ((m + n) % 2 == 1) {// 奇数长度，中位数是左半部分最大值return Math.max(nums1_left, nums2_left);
} else {// 偶数长度，中位数是左右部分的中间值平均return (Math.max(nums1_left, nums2_left) + Math.min(nums1_right, nums2_right)) / 2.0;
}

完整代码（Java）

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int m = nums1.length, n = nums2.length;// 确保 nums1 是较短的数组，优化二分范围if (m > n) {int[] temp = nums1;nums1 = nums2;nums2 = temp;m = nums1.length;n = nums2.length;}int left = 0, right = m;while (left < right) {// 向上取整，避免死循环int mid = (left + right + 1) / 2; int j = (m + n + 1) / 2 - mid;if (nums1[mid - 1] > nums2[j]) {// i 太大，左移右边界right = mid - 1;} else {// i 太小，右移左边界left = mid;}}int i = left;int j = (m + n + 1) / 2 - i;// 处理边界值：左半部分或右半部分为空的情况double nums1_left = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];double nums1_right = (i == m) ? Integer.MAX_VALUE : nums1[i];double nums2_left = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];double nums2_right = (j == n) ? Integer.MAX_VALUE : nums2[j];// 计算中位数if ((m + n) % 2 == 1) {return Math.max(nums1_left, nums2_left);} else {return (Math.max(nums1_left, nums2_left) + Math.min(nums1_right, nums2_right)) / 2.0;}}
}