leetcode 4. Median of Two Sorted Arrays详解

4. Median of Two Sorted Arrays

description:

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3] nums2 = [2] The median is 2.0

Example 2:

nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5

解答

中位数是整个序列从小到大排列，位置处于最终间的数。

本道题是求两个已经排好序的数组的中位数

假设一个数组为A，另一个数组为B

那么中位数把数组A，B的左边和右边分为两块，让左边的大小和右边的大小相等。

如下图所示。

左边右边A[0], A[1], …, A[i-1]A[i], A[i+1], …, A[m-1]B[0], B[1], …, B[j-1]B[j], B[j+1], …, B[n-1]

其中A[i-1] 小于 A[i]（已知），B[j-1] 小于 B[j]（已知）， A[i-1]小于B[j]，B[j-1]小于A[i]

假设数组A的长度为m，数组B的长度为n ,m的左边有i个，n的左边有j个，则i + j = m - i + n - j + 1，所以j = $\frac{m+n+1}{2}-i$

为了保证j > 0，我们需要保证$\frac{m+n+1}{2}-i$，所以我们需要保证m小于n。

所以本算法的精髓就是通过对i进行二分查找来找到一个i，满足 A[i-1] 小于 B[j] ，B[j-1] 小于 A[i] 时，即可以把两个数组划分为等长的两部分，即可以找到中位数。

当找到的i使得 A[i - 1] > B[j] 时，说明i过大，我们应该在i的左边进行二分查找。

当找到的i使得A[i] < B[j - 1] 时，说明i过小，我们应该在i的右边进行二分查找。

这里需要注意，当i等于0的时候 A[i - 1] 不存在，当 i = m 时 A[i] 不存在，j也是如此，所以我们需要对这些边界条件进行特殊处理。

最后根据m + n的奇偶性进行返回，当m + n为奇数时，返回左边的最大值，当m + n为偶数时，返回$\frac{左边的最大值+右边的最大值}{2}$

代码

class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { if (nums1.size() > nums2.size() ) return findMedianSortedArrays(nums2, nums1); auto m = nums1.size(); auto n = nums2.size(); int lo = 0, hi = m, halfLen = (m + n + 1) / 2; while (lo <= hi) { auto i = (lo + hi) / 2; auto j = halfLen - i; //当i等于m时，j可能为0，nums2[j - 1]不存在 if (i < m && nums1[i] < nums2[j - 1] ) lo = i + 1; //当i等于0时，nums1[i - 1]不存在 else if (i > 0 && nums1[i - 1] > nums2[j]) hi = i - 1; else{ int leftMax = 0; int rightMin = 0; //先求左边的最大值，如果m + n为奇数，则左边的最大值就是中位数，直接返回 if (i == 0) { leftMax = nums2[j - 1]; } else if (j == 0) { leftMax = nums1[i - 1]; } else { leftMax = max(nums1[i - 1], nums2[j - 1]); } if ((m + n) % 2 == 1) return leftMax; //求右边的最大值 if (i == m) { rightMin = nums2[j]; } else if (j == n) { rightMin = nums1[i]; } else { rightMin = min(nums2[j], nums1[i]); } return (leftMax + rightMin) / 2.; } } return -1; } };