这是LeetCode的第四题
题目
这道题的要求是找出数组长度为m和n的两个有序数组nums1和nums2的中位数.m和n不同时等于0.
并且要求算法复杂度为O(log(m+n))
题解
根据题目要求我们不难看出这道题应该用二分查找来解决.题目中要求找中位数.
令
\[left\_part= left\_part(nums1)+left\_part(nums2)\\right\_part=right\_part(nums1)+right\_part(nums2)\]
于是题目等价于找到
\[ \mbox{当m+n为偶数时, }len(left\_part)=len(right\_part)\\\mbox{当m+n为奇数时, }len(left\_part)=len(right\_part)+1\\max(left\_part)\leqq min(right\_part)\]
即,确定游标\(i\)和\(j\)的值,将\(nums1\)和\(nums2\)分别划分成符合上式的两个部分
我们可以假定\(m\leqq n\)(如果m>n,可以调换nums1和nums2)
\[half\_len:=len(left\_part)=\frac{m+n+1}{2}\tag{1}\]
现在我们来讨论一下游标的含义.
使用\(i\)和\(j\)将\(nums1\)和\(nums2\)分成两个部分,由于数组下标从0开始,所以nums1[i]的有如下含义:
\[i = len(left\_part(nums1))\Rightarrow i\in [0,m]\tag{2}\]
当然,\(nums1[m]\)并不存在,在这里我们假定有一个\(nums1[m]\),但实际上我们不会访问到\(nums1[m]\)中的值.
将\(nums1[m]\)作为哨兵,这样可以省去讨论边界条件的麻烦.当\(i=m\)时表明\(nums1\)中所有元素属于\(left\_part(nums1)\)
\[j = len(left\_part(nums2))=half\_len-i\tag{3}\\\mbox{由(1)和(2)可得}\\j = \frac{m+n+1}{2}-i\]
由于m和n都是已知,并且\(j\)可以由\(i\)推导出.
综上,此题就转化成了在\(nums1\)中找\(i\)的问题.
最高效的方法就是使用二分查找来找\(i\),初始条件为:
\[begin = 0\\end = m\\i = \frac{begin+end}{2}\]
找到\(nums[i]\)后,可以分成以下三种情况
- \(i>0,nums1[i-1]>nums2[j]\Rightarrow i\mbox{太大}\),在\([begin,i)\)内搜索
- \(i<m,nums1[i]<nums2[j-1]\Rightarrow i\mbox{太小}\),在\((i,end]\)内搜索
- 若上述两种情况都不成立,\(i\)符合条件,搜索停止
此时我们得到了\(i\)符合划分要求,接下来就是找中位数
- 如果m+n为奇数,那么中位数为\(max(left\_part)\)
- 如果m+n为偶数,那么中位数为\(\frac{max(left\_part)+min(right\_part)}{2}\)
关于\(max(left\_part)\)的求解,
- 如果\(i=0\),那么可知\(max(left\_part)=nums2[j-1]\)
- 如果\(j=0\),那么可知\(max(left\_part)=nums1[i-1]\)
- 一般情况,\(max(left\_part)=max(nums1[i-1],nums2[j-1])\)
同理可获得\(min(right\_part)\)
复杂度分析
- 计算复杂度: \(O(\log(max(m,n)))\)
- 空间复杂度:\(O(1)\)
实现代码
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size();
int n = nums2.size();
if(m>n) // 确保m>n
{
return findMedianSortedArrays(nums2, nums1);
}
int halfLen = (m+n+1)/2;
int i,j,begin = 0,end= m;
double rval= 0.0;
while(begin<=end)
{
i = (begin+end)/2;
j = halfLen-i;
if(i<m&&nums1[i]<nums2[j-1])
{
begin = i+1;
}
else if(i>0&&nums1[i-1]>nums2[j])
{
end = i-1;
}
else
{
int maxLeft,minRight;
if(i==0){
maxLeft = nums2[j-1];
}else if (j==0)
{
maxLeft = nums1[i-1];
}else{
maxLeft = nums1[i-1]>nums2[j-1]?nums1[i-1]:nums2[j-1];
}
if((m+n)%2==1)
{
rval = maxLeft;
break;
}
if(i==m)
{
minRight = nums2[j];
}else if (j==n)
{
minRight = nums1[i];
}else
{
minRight = nums1[i]<nums2[j]?nums1[i]:nums2[j];
}
rval = ((double)(maxLeft+minRight))/2;
break;
}
}
return rval;
}
};