O(lgk)解法Find the k-th Smallest in Two Sorted Arrays - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

O(lgk)解法Find the k-th Smallest in Two Sorted Arrays

O(lgk)解法Find the k-th Smallest in Two Sorted Arrays# JobHunting - 待字闺中

f*42011-08-16 07:08

1 楼

O(m+n), O(k), O(lg m + lg n)解法见
http://www.ihas1337code.com/2011/01/find-k-th-smallest-element-
O(lgk)的解法只是2分查找需要查找的范围，而不是0～m或者0～n
文字解释可以看我的回答
http://www.mitbbs.com/article_t1/JobHunting/31911109_0_1.html
#include
bool try_find_kth(int a[], int lowa, int higha, int b[], int lowb, int highb
, int k)
{
while(lowa<=higha)
{
int mid=lowa+(higha-lowa)/2;
if(a[mid]b[k-mid-2]))
{
printf("find %dth %d\n",k,a[mid]);
return true;
}
else
if(a[mid]>b[k-mid-1])
higha= mid-1;
else // a[mid>b[k-mid-2]]]
lowa = mid+1;
}
return false;
}
void find_kth(int a[], int lena, int b[], int lenb, int k)
{
if (k<1||lena+lenb < k)
return;
int lowa=-1, higha, lowb=-1, highb;
// can be simplified, but following is easy to understand
if(lena>=k)
{
lowa = 0;
higha = k-1;
}
if(lenb>=k)
{
lowb = 0;
highb = k-1;
}
if(lowa==-1 && lowb==-1)
{
lowa=k-lenb-1;
higha=lena-1;
lowb=k-lena-1;
highb=lenb-1;
}
else
{
if(lowa==-1)
{
lowa=0;
higha=lena-1;
}
if(lowb==-1)
{
lowb=0;
highb=lenb-1;
}
}
//if(!try_find_kth(a,lowa,higha,b,lowb,highb,k))
try_find_kth(b,lowb,highb,a,lowa,higha,k);
}
void dump(int a[],int lena)
{
for(int i=0; iprintf("%d ",a[i]);
printf("\n");
}
void test3()
{
int a[]={1,3,6,9,12,15,18,21};
int b[]={2,4,8,10,14,16};
dump(a,8);
dump(b,6);
find_kth(a,8,b,6,1);
find_kth(a,8,b,6,2);
find_kth(a,8,b,6,3);
find_kth(a,8,b,6,4);
find_kth(a,8,b,6,5);
find_kth(a,8,b,6,6);
find_kth(a,8,b,6,7);
find_kth(a,8,b,6,8);
find_kth(a,8,b,6,9);
find_kth(a,8,b,6,10);
find_kth(a,8,b,6,11);
find_kth(a,8,b,6,12);
find_kth(a,8,b,6,13);
find_kth(a,8,b,6,14);
}
void test4()
{
int a[]={2,4,8,10,14,16};
int b[]={1,3,6,9,12,15,18,21};
dump(a,6);
dump(b,8);
find_kth(a,6,b,8,1);
find_kth(a,6,b,8,2);
find_kth(a,6,b,8,3);
find_kth(a,6,b,8,4);
find_kth(a,6,b,8,5);
find_kth(a,6,b,8,6);
find_kth(a,6,b,8,7);
find_kth(a,6,b,8,8);
find_kth(a,6,b,8,9);
find_kth(a,6,b,8,10);
find_kth(a,6,b,8,11);
find_kth(a,6,b,8,12);
find_kth(a,6,b,8,13);
find_kth(a,6,b,8,14);
}
int main()
{
test3();
test4();
}

f*42011-08-16 07:08

2 楼

当k接近m,n的时候，并不比O(lg m + lg n)的方法快多少
但当k<

f*42011-08-16 07:08

3 楼

修改了一下try_find_kth函数，新的函数可以同时handle O(lgn+lgm)和O(lgk)的情况
bool try_find_kth(int a[], int lowa, int higha, int b[], int lowb, int highb
, int k)
{
while(lowa<=higha)
{
int mid=lowa+(higha-lowa)/2;
if (mid>=k)
{
higha=mid-1;
continue;
}
if(a[mid]b[k-mid-2]))
{
printf("find %dth %d\n",k,a[mid]);
return true;
}
else
if(a[mid]>b[k-mid-1])
higha= mid-1;
else // a[mid>b[k-mid-2]]]
lowa = mid+1;
}
return false;
}
void find_kth(int a[], int lena, int b[], int lenb, int k)
{ //O(lgk)
if (k<1||lena+lenb < k)
return;
int lowa=-1, higha, lowb=-1, highb;
if(lena>=k)
{
lowa = 0;
higha = k-1;
}
if(lenb>=k)
{
lowb = 0;
highb = k-1;
}
if(lowa==-1 && lowb==-1)
{
lowa=k-lenb-1;
higha=lena-1;
lowb=k-lena-1;
highb=lenb-1;
}
else
{
if(lowa==-1)
{
lowa=0;
higha=lena-1;
}
if(lowb==-1)
{
lowb=0;
highb=lenb-1;
}
}
if(!try_find_kth(a,lowa,higha,b,lowb,highb,k))
try_find_kth(b,lowb,highb,a,lowa,higha,k);
}
void find_kth1(int a[], int lena, int b[], int lenb, int k)
{//O(lgm+lgn)
if (k<1||lena+lenb < k)
return;
if(!try_find_kth(a,0,lena-1,b,0,lenb-1,k))
try_find_kth(b,0,lenb-1,a,0,lena-1,k);
}