首页 > 代码库 > [leetcode]Median of Two Sorted Arrays
[leetcode]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)).
基本思想：
此题思想很简单，设定两个指针，从两个数组的开始一个个比较并适当的移动指针，直到找到中位数。
需要注意的一点是：中位数的定义。数据总和为偶数时，中位数如何处理？(在面试中，这个最好要对面试官问清楚。)此题的处理是采用两个中位数的平均值
代码：
double findMedianSortedArrays(int A[], int m, int B[], int n) { //C++
int pre = 0;
int midpos = (m+n)/2;
bool isodd = (m+n)%2 == 1;
if(n == 0)
{
if(isodd)
return A[(m-1)/2];
else
return ((double)A[(m-1)/2]+(double)A[(m-1)/2+1])/2;
}
if(m == 0)
{
if(isodd)
return B[(n-1)/2];
else
return ((double)B[(n-1)/2]+(double)B[(n-1)/2+1])/2;
}
int pa = 0, pb = 0;
double median;
int nextmed = 0;
if(isodd)
{
while(pre != midpos+1 && pa < m&& pb < n )
{
if(A[pa] < B[pb])
{
median = A[pa];
pa++;
}
else
{
median = B[pb];
pb++;
}
pre++;
}
if(pre < midpos+1)
{
if(pa == m)
return B[midpos-pre+pb];
else return A[midpos-pre+pa];
}
return median;
}
else
{
while(pre != midpos && pa < m&& pb < n )
{
if(A[pa] < B[pb])
{
median = A[pa];
pa++;
}
else
{
median = B[pb];
pb++;
}
pre++;
}
if(pre < midpos)
{
if(pa == m)
return ((double)B[midpos-pre+pb-1]+(double)B[midpos-pre+pb])/2;
else return ((double)A[midpos-pre+pa-1]+(double)A[midpos-pre+pa])/2;
}
else
{
if(pa == m)
return ((double)median + B[pb])/2;
else if(pb == n)
return ((double)median + A[pa])/2;
else {
nextmed = (A[pa] > B[pb])? B[pb]:A[pa];
return ((double)median + nextmed)/2;
}
}
}
}[leetcode]Median of Two Sorted Arrays
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。