题目链接
解析
两个有序数组如何求中位数呢?把两个有序数组排序?将两个有序数组排序的时间复杂度至少为\(O(m+n)\),不符合时间复杂度\(O(log(m+n))\)的要求。
本题需用到的两个点:
- 由\(O(log(m+n))\)可知需要用二分法,
- 中位数的性质,小于中位数的数的数量和大于中位数的数的数量一样多。
假如我们在数组1中找到一个切分点mid1
,同时由中位数的性质在数组2中确定一个切分点mid2
,若两个切分点满足:数组1中mid1
左侧的数+数组2中mid2
左侧的数均小于数组1中mid1
右侧的数+数组2中mid2
右侧的数,那么这两个切分点就成功将两个数组划分为两部分,两部分数量相等,且其中一部分的数均小于另一部分,即可从中得到中位数。
复杂度
只需要二分查找较小的数组,所以时间复杂度为\(O(\min(m,n))\)。
实现
C++
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len1 = nums1.size(), len2 = nums2.size();
if (0 == len1) // 处理特殊情况
return len2 % 2 == 0 ? (double(nums2[len2 / 2 - 1]) + double(nums2[len2 / 2])) / 2 : nums2[len2 / 2];
if(0 == len2)
return len1 % 2 == 0 ? (double(nums1[len1 / 2 - 1]) + double(nums1[len1 / 2])) / 2 : nums1[len1 / 2];
if (len1 > len2) // 只二分查找较小的数组
return findMedianSortedArrays(nums2, nums1);
int len = len1 + len2;
int low = 0, high = len1, k = len >> 1;
int mid1, mid2, left1, right1, left2, right2;
while (1) {
mid1 = low + ((high - low) >> 1); // 确定切分点mid1
mid2 = k - mid1; // 根据中位数性质确定切分点mid2
left1 = mid1 == 0 ? INT_MIN : nums1[mid1 - 1]; // 需要处理边界点
right1 = mid1 == len1 ? INT_MAX : nums1[mid1];
left2 = mid2 == 0 ? INT_MIN : nums2[mid2 - 1];
right2 = mid2 == len2 ? INT_MAX : nums2[mid2];
if (left1 > right2) high = mid1 - 1; // 左移
else if (left2 > right1) low = mid1 + 1; // 右移
else {
if (len % 2 == 0) return (double(max(left1, left2)) + double(min(right1, right2))) / 2; // 偶数情况
else return min(right1, right2); // 奇数情况
}
}
}
};