Median of Two Sorted Arrays

0
0
0
1. 云栖社区>
2. 博客>
3. 正文

## Median of Two Sorted Arrays

There are two sorted arrays A and B 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)).

题解：

这样整个问题就迎刃而解了。

int partA = Math.min(k/2,m);
int partB = k - partA;

为了能保证上面的分半操作正确，需要保证A数组的长度小于B数组的长度。

C++实现代码：

```#include<iostream>
using namespace std;

class Solution {
public:
double findMedianSortedArrays(int A[], int m, int B[], int n) {
int total=m+n;
if((m+n)%2)
return findMedian(A,0,m-1,B,0,n-1,total/2+1);
else
{
int pre=findMedian(A,0,m-1,B,0,n-1,total/2);
int last=findMedian(A,0,m-1,B,0,n-1,total/2+1);
return (pre+last)/2;
}
}
double findMedian(int A[],int astart,int aend,int B[],int bstart,int bend,int k)
{
int m=aend-astart+1;
int n=bend-bstart+1;
if(m>n)
return findMedian(B,bstart,bend,A,astart,aend,k);
if(m==0)
return B[k-1];
if(k==1)
return min(A[astart],B[bstart]);
int partA=min(m,k/2);
int partB=k-partA;
if(A[astart+partA-1]<B[bstart+partB-1])
return findMedian(A,astart+partA,aend,B,bstart,bend,k-partA);
else if(A[astart+partA-1]>B[bstart+partB-1])
return findMedian(A,astart,aend,B,bstart+partB,bend,k-partB);
else
return A[astart+partA-1];
}
};

int main()
{
Solution s;
int A[5]= {1,2,3,4,5};
int B[10]= {6,7,8,9};
cout<<s.findMedianSortedArrays(A,4,B,4)<<endl;
}```

```#include<iostream>
using namespace std;

class Solution
{
public:
double findMedianSortedArrays(int A[], int m, int B[], int n)
{
int i=0, j=0, median = m+n;
double prev=0, last=0;

if(median<2)
{
if (m == 0 && n == 0) return 0;
if (m==1)
return A[0];
else
return B[0];
}

while ( (i+j) <= (median/2) )
{
prev = last;
if (i >= m) //如果A中的元素已经用完，直接取B数组
{
last=B[j];
j++;
}
else if (j>=n) //同上
{
last = A[i];
i++;
}
else if (A[i]<B[j]) //取A[i] 和 B[j] 中较小的
{
last = A[i];
i++;
}
else
{
last=B[j];
j++;
}
}

if ((median & 1) == 0) //偶数个
return (prev + last) / 2.0;
else //奇数个
return last;
}
};

int main()
{
Solution s;
int A[5]= {1,2,3,4,5};
int B[10]= {6,7,8,9};
cout<<s.findMedianSortedArrays(A,5,B,4)<<endl;
}```

+ 关注