Â¥Ö÷

[ÌÖÂÛ]Ò»µÀ±±´óCS¿¼ÑÐÌâ ÓÐÁ½¸ö£¨µÝÔö£©ÓÐÐòÊý×éAºÍB£¬³¤¶È¾ùΪn¡£Îª¼òµ¥Æð¼û£¬²»·ÁÉèÕâ2n¸öÊýÈ«ÊÇ»¥ÒìµÄÕûÊý¡£ Éè¼ÆÒ»¸öËã·¨£¬ÄÜÔÚO(log n)ʱ¼äÄÚÕÒµ½Á½¸öÊý×é¡°ºÏ²¢ºóµÄÖÐÊý¡±¡£¼´£¬¼ÙÉèÕâ2n¸öÊýÒѾ­¹é²¢³ÉÁËÒ»¸ö³¤¶ÈΪ2nµÄÓÐÐòÊý×éC£¨C[0],...,C[2n-1]£©¡£ ¡°ºÏ²¢ºóµÄÖÐÊý¡±x=(C[n-1]+C[n])/2¡£Êä³öÕâ¸öx¡£    Êղؠ  ·ÖÏí   ¶¥(0)

----------------------------------------------
Three passions, simple but overwhelmingly strong, 
have governed my life: the longing for love, the
search for knowledge, and unbearable pity for the
suffering of mankind.
                            - Bertrand Russell

	µÚ2Â¥

Õâ¸öÊÇÔ­Ìâô£¿¸Ð¾õO(logn)²»´ó¿ÉÄܵÄ˵

----------------------------------------------
phoenixinter
algorithm bm@lilybbs
ikki@poj

	µÚ3Â¥

ÊÇ»ØÒäÌâ¡£O(log n)ÕâÀïÓ¦¸Ãû´í¡£ ÒòΪԭÌ⻹ҪÇóÖ¤Ã÷log n½×ÊÇ×îÓŵģ¨Õâ¸öµ±È»ºÜ¼òµ¥£©¡£ »¥ÒìµÄÌõ¼þÊÇÎҼӵġ­¡­

----------------------------------------------
Three passions, simple but overwhelmingly strong, 
have governed my life: the longing for love, the
search for knowledge, and unbearable pity for the
suffering of mankind.
                            - Bertrand Russell

	µÚ4Â¥

Say the two arrays are sorted and increasing, namely A and B. It is easy to find the median of each array in O(1) time. Assume the median of array A is m and the median of array B is n. Then, 1' If m=n, then clearly the median after merging is also m, the algorithm holds. 2' If m<n, then reserve the half of sequence A in which all numbers are greater than    m, also reserve the half of sequence B in which all numbers are smaller than n.    Run the algorithm on the two new arrays. 3' If m>n, then reserve the half of sequence A in which all numbers are smaller than    m, also reserve the half of sequence B in which all numbers are larger than n.    Run the algorithm on the two new arrays. Time complexity: O(logn)

----------------------------------------------
phoenixinter
algorithm bm@lilybbs
ikki@poj

	µÚ5Â¥

nod. ºÃ°ì·¨¡£ ^_^

----------------------------------------------
Three passions, simple but overwhelmingly strong, 
have governed my life: the longing for love, the
search for knowledge, and unbearable pity for the
suffering of mankind.
                            - Bertrand Russell

	µÚ6Â¥

#include <iostream> using namespace std ; int main(){  cout<<"Enter size of the array:";  int size;  cin>>size;  int * a= new int[size];  int * b= new int[size];  cout<<"Enter array A:";  for(int i=0;i<size;i++)   cin>>a[i];  cout<<"Enter array B:";  for(i=0;i<size;i++)   cin>>b[i];  if(a[0]>b[size-1]){   cout<<(a[0]+b[size-1])/2<<endl;   delete [] a;   delete [] b;   return 0;  }  if(b[0]>a[size-1]){   cout<<(b[0]+a[size-1])/2<<endl;   delete [] a;   delete [] b;   return 0;  }  int as,bs,ae,be;  as=bs=0;  ae=be=(size-1);  while(1)  {   if((as+1)==ae)break;   if(a[(as+ae)/2]>b[(size-1)-(as+ae)/2]){    ae=(as+ae)/2;   }   else if(a[(as+ae)/2]<b[(size-1)-(as+ae)/2]){    as=(as+ae)/2;   }  }  int tmp_min=(a[ae]<b[(size-1)-as])?a[ae]:b[(size-1)-as];  int tmp_max=(a[as]>b[(size-1)-ae])?a[as]:b[(size-1)-ae];  cout<<(tmp_min+tmp_max)/2<<endl;  delete [] a;  delete [] b;  return 0; }

	µÚ7Â¥

ÔÞ´ó¼Ò£¡£¡

	µÚ8Â¥

ºÃ£¡

	µÚ9Â¥

ÉÆ£¡ ³¤¼ûʶÁË

	µÚ10Â¥

int tmp_min=(a[ae]<b[(size-1)-as])?a[ae]:b[(size-1)-as]; int tmp_max=(a[as]>b[(size-1)-ae])?a[as]:b[(size-1)-ae] ÊDz»ÊÇ·´ÁË »¹ÓÐÄܲ»ÄÜ°ÑËã·¨µÄÔ­Àí˵Ã÷Ò»ÏÂ

----------------------------------------------
ieee.org.cn