作者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