int findnth(int* a,int* b,int l1,int r1,int l2,int r2)
{
int t1,t2;
int result;
int nth=r1-l1+1;
int middle=(nth+1)/2;
if(nth==1||a[middle-1+l1]==b[middle-1+l2])
return a[middle-1+l1]<=b[middle-1+l2]?a[middle-1+l1]:b[middle-1+l2];
if(a[middle-1+l1]<b[middle-1+l2])
{
if(nth%2==0)
{
t1=middle+l1,t2=middle-1+l2;
}
else
{
t1=middle-1+l1,t2=middle-1+l2;
}
result=findnth(a,b,t1,r1,l2,t2);
}
else
{
if(nth%2==0)
{
t1=middle-1+l1,t2=middle+l2;
}
else
{
t1=middle-1+l1,t2=middle-1+l2;
}
result=findnth(a,b,l1,t1,t2,r2);
}
return result;
}
先求第N小的数，第N大的数刚好排在它前面。
首先，比较A的中位数和B的中位数，不妨设A[n/2]> B[n/2],则所求必在A[1...n/2]和B[n/2...n]之中。再比较后面两个数组的中位数，以此迭代，每次查找范围缩小一半，故运行时间O(logN).
举例：A={1，2，3，6，7}，B={0，4，5，8，9}
第一次比较3和5，得到下一次查找范围{3，6，7}和{0，4，5}
第二次比较6和4，得到{3,6}和{4，5}
第三次比较3和4，得到{6}和{4}
最后检查6和4对应的下标，可以确定是4.
因此第N大的数应是5和6中较小的一个，即所求为5。 |
|
转播
