两个已排序的数组,个数相同且都为n,求在lgn时间内求出两数组共同的中位数。
思路:分别求出两数组的中位数mid1,mid2,如果相等则即为所求中位数,如果mid1<mid2,则取第一个数组的后半部分,第二个的前半部分,否则相反。递归调用这一过程,直到每一个数组中只有一个数字,则取这两个数字中较小的(默认为下中位数)数字为两个数组的中位数。
代码如下:
#include<iostream> using namespace std; //找出下标从p到r范围之间的中位数 int FindMid(int a[],int p,int r) { int length=r-p+1; int mid=(length+1)/2; return a[p+mid-1]; } int SelectMid(int a[],int b[],int length,int p1,int r1,int p2,int r2) { int mid1,mid2; //如果某一数组中只剩下一个元素,则该元素即为中位数 if(r1-p1==0) { return a[p1]; } if(r2-p2==0) { return b[p2]; } mid1=FindMid(a,p1,r1); mid2=FindMid(b,p2,r2); if(mid1==mid2) { return mid1; } //如果mid1大于mid2则取a中下标范围内的的前半部分,b中小标范围内的后半部分 else if(mid1>mid2) { r1=p1+(r1-p1)/2; p2=p2+(r2-p2)/2; } //如果mid1大于mid2则取a中下标范围内的的hou半部分,b中小标范围内的前半部分 else { r2=p2+(r2-p2)/2; p1=p1+(r1-p1)/2; } //递归调用该函数知道找到中位数为止 SelectMid(a,b,r1-p1+1,p1,r1,p2,r2); } int main() { int a[10]={1,3,5,7,9,11,13,15,17,19}; int b[10]={2,4,6,8,10,12,14,16,18,20}; int mid=SelectMid(a,b,10,0,9,0,9); cout<<mid<<endl; return 0; }