作者swon (囧興囧九囧rz)
看板Grad-ProbAsk
標題Re: [理工] 97東華資結
時間Sat Apr 11 02:13:01 2009
※ 引述《fish0835 (以無用為大用)》之銘言：
: ※ 引述《InitialShuk (Shuk)》之銘言：
: : X Y為兩個sorted好的 含n element的array
: : 請用O(logN)的algo 找出 X聯集Y之中間值
: : 目前只想到O(N) .....
: 假設X,Y是由小至大排好的array
: steps:
: 1.把X,Y的中間值a,b拿來比較
: 2.不失其一般性的假設 a < b ，則將X的左半部與Y的右半部刪去。
: 3.重復 1~2 直到找到中間值
: time complexity:
: 每次皆刪去一半的不可能之情況，所以時間函數為...
: T(n) = T(n/2) + O(1)
: = O(lg n) //n為X聯集Y之長度
: 有錯請各位大大更正囉^^
想法是二分搜尋法~
不過要搜尋的對象有些條件
就 X 中的元素 X[k] 而言
我們會發現在 X Array 當中有 k 個元素會小於等於 X[k]
現在我們要找到 X Y Array 的中位數
(X Y 中共有 n 個數小於等於他們的中位數)
所以我們需要確認在 Y 中是不是恰好有 (n-k) 個元素小於等於 X[k]
(這樣子在 X Y 中總共會有 k+(n-k)=n 個元素小於等於 X[k]，則 X[k] 為所求)
* 結論：要找到一個 X[k] 使得 Y[n-k] <= X[k] <= Y[n-k+1]
程式碼跟二元搜尋差不多，加些條件即可：
int FindMedian(int X[], int Y[], int n, int low, int high)
{
if( low > high)
{
return -1;
}
else
{
int k=(low+high)/2;
if((k==n && X[k]<=Y[0])|| (X[k]>=Y[n-k-1] && X[k]<=Y[n-k])) return X[k];
//邊界情形 //一般情形
else if(X[k]<Y[n-k-1]) return FindMedian(X,Y,n,k+1,high);
else return FindMedian(X,Y,n,low,k-1);
}
}
時間複雜度：2n個元素做二分搜尋法，依舊是：O(logn)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.55.192